個数制限付きナップザック問題です。
問題概要
原文 → Knapsack Problem with Limitations | Aizu Online Judge
価値 で重さ であるような 種類の品物と、容量が のナップザックがある。
番目の品物は 個まで使用できる。
ナップザックの容量を超えないように品物を入れた時の価値の最大値を求めよ。
解説
各品物について、品物を 個入れたとき、 個入れたとき・・・と愚直に ずつ増やして考えていくと計算量的に間に合いません。
そこで、繰り返し二乗法のように(厳密には少し違うけど)、取る数を 倍ずつ増やしていくことで考えていきましょう。
例えば品物が 個ある場合は、この場合ですと
- 品物を 個入れたとき
- 品物を 個入れたとき
- 品物を 個入れたとき
- 品物を 個入れたとき
をそれぞれ計算するというわけですね。これで計算量が となり間に合います。
ソースコード
for 文の向きに気をつけましょう。
signed main() { int N, W; cin >> N >> W; int v[110], w[110], m[110]; rep(i,0,N) cin >> v[i] >> w[i] >> m[i]; int dp[10010] = {}; rep(i,0,N) { // take key good(s) each for(int k=0; m[i]>0; k++) { int key = min(m[i], (int)(1<<k)); m[i] -= key; for(int j=W; j>=key*w[i]; j--) { // do not take or take dp[j] = max(dp[j], dp[j-key*w[i]] + key*v[i]); } } } int ans = 0; repq(i,0,W) ans = max(ans, dp[i]); cout << ans << endl; return 0; }