個数制限付きナップサック問題を勉強しました
問題概要
価値が vi 重さが wi であるような N 種類の品物と、容量が W のナップザックがあります。i 番目の品物は mi 個まで選ぶことができます。選んだ品物の重さの総和が W を超えないように選んだとき、価値の合計の最大値を求めてください。
問題リンク Knapsack Problem with Limitations | Aizu Online Judge
制約
- 1 ≦ N ≦ 100
- 1 ≦ vi, wi ≦ 1000
- 1 ≦ mi ≦ 10000
- 1 ≦ W ≦ 10000
解法
品物の合計が Nm 個あるので単純なナップサックDPでは O(NmW) となり、このままでは解けません。
工夫をして i 番目の品物を 1, 2, 4, 8,..., 2k, r 個ずつに分割してまとめてみます (rは余り)。するとこれらの組み合わせで 1,2,3,...,mi 個だけ品物を入れることを表現できます。これで m をlog m 個にまとめられるので計算量は O(NWlogm) となり、これは間に合います。
Code
#include <bits/stdc++.h> using namespace std; #define REP(i, n) for (int i = 0; i < n; i++) int N, W, M, dp[2000][10005]; vector<int> v, w; int main() { cin >> N >> W; REP(i,N){ int vi, wi, m, b=1; cin >> vi >> wi >> m; // divide m into 1, 2, 4, 8... while(b<=m){ v.push_back(vi*b); w.push_back(wi*b); m -= b; b *= 2; } // the rest of m if(m>0){ v.push_back(vi*m); w.push_back(wi*m); } } M = v.size(); REP(i,M){ REP(j,W+1){ dp[i+1][j] = max(dp[i+1][j], dp[i][j]); if(j >= w[i]) dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i]); } } cout << dp[M][W] << endl; return 0; }