【AOJ DPL1】B: Combinatorial - 0-1 Knapsack Problem

問題

ナップザック問題 | 動的計画法 | Aizu Online Judge

方針

• 各要素を入れる, 入れないというパターンを試して価値を高める.
• ただし, すべての商品に対して上のパターンを試すととなるため終わらない.
• 動的計画法を用いることにより, にまで落とすことができる.
• i個までのものを使って重さjのナップサックに詰めたときの最大値 として計算する.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;
 
signed main(){
  int w[1001];
  int v[1001];
  int dp[101][10001];
  int N, W;
  cin >> N >> W;
  REP(i, 1, N+1){
    cin >> v[i] >> w[i]; 
  }
  rep(i, 101){
    rep(j, 1001){
      dp[i][j] = 0;
    }
  }
 
  REP(i, 1, N+1){
    REP(j, 1, W+1){
      if(j >= w[i]){
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
      }else{
        dp[i][j] = dp[i-1][j];
      }   
    }
  }
   
  cout << dp[N][W] << endl;
}