読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj DPL_1_C

Knapsack Problem | Aizu Online Judge
0/1ナップサック問題とループの向きが単に逆になったパターン.
今回は中間結果の情報は破棄しているが問題によっては必要になる.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)

using namespace std;

int main()
{
  int n, W; cin >> n >> W;
  vector<int> v(n);
  vector<int> w(n);
  REP(i,n) cin >> v[i] >> w[i];
  vector<int> dp(10001,0);
  dp[0] = 0;
  REP(i,n) FOR(j,w[i],W)
    dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
  cout << *max_element(dp.begin(),dp.begin()+W+1) << endl;
  return 0;
}