DPL_1_C

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C

制限なしナップサック

解法：漸化式に沿ってO(N*W)

漸化式の立て方は

threestones.hateblo.jp

こちらを参考にした。

なかなかこの漸化式に変形しきれないので今のうちは覚えておくほうが吉なのか

#include <iostream>
using namespace std;
int main(){
  int n,mw;
  int v[1005],w[1005];
  cin >> n >> mw;
  for(int i=0;i<n;i++){
    cin >> v[i] >> w[i];
  }
  int dp[mw+2][n];
  fill(&dp[0][0],&dp[mw+1][n-1],0);
  for(int i=1;i<=mw;i++){
    for(int j=0;j<n;j++){
      dp[i][j] = i-w[j]>=0?max(dp[i][j-1],dp[i-w[j]][j]+v[j]):dp[i][j-1];
    }
  }
  cout << dp[mw][n-1] << endl;
}