動的計画法

値を覚えて再利用

ナックサック問題

価値と重さの組み合わせの品がN個ある。
ナックサックの容量は決まってあり、容量の限界まで入れた場合の品の最大の価値を求めよう。

入力例

n=4 //品の個数
w={2,1,3,2} //weight
v={3,2,4,2} //value
W=5 //容量

コード

#include <iostream>
#include <string.h>
using namespace std;

int n, W;
int w[5], v[5];//int w[MAX_N], v[MAX_N];
int dp[5][6];//int dp[MAX_N + 1][MAX_W + 1];

int rec(int i, int j) {
  if (dp[i][j] >= 0) {//dpの要素は-1で初期化されているので
                      //dpが-1でない -> dpに値が入っている
    return dp[i][j];//スキップ
  }
  int res;
  if (i == n) {
    res = 0;
  } else if (j < w[i]) {
    res = rec(i  + 1, j);
  } else {
    res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
    //rec(i + 1, j)dpで下の値
    //rec(i + 1, j - w[i]) + v[i])dpで下の値で品の重さだけ位置を引いた値+価値
    //n個の品で0からn個の品までRESをdp[i][j]に決める全探索を実行する。
  }
  return dp[i][j] = res;//メモ
}

void solve(){
  memset(dp, -1, sizeof(dp));//dpが-1で初期化
  cout<< "Max value = ";
  printf("%d\n", rec(0, W));
}

int main() {
  cout<< "n = ";
  cin >> n;
  int MAX_N = n,a,b;
  //int w[MAX_N], v[MAX_N];
  for(int i = 0;i<n;i++){
    cout<< "w v = ";
    cin >> a >> b;
    w[i] = a;
    v[i] = b;
  }
  cout<< "W = ";
  cin >> W;
  solve();
}

実行結果

n = 4
w v = 2 3
w v = 1 2
w v = 3 4
w v = 2 2
W =  5
Max value = 7