背包九講之八：背包問題求方案數
有 N 件物品和一個容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的體積是 vi，價值是 wi。
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出 最優選法的方案數。注意答案可能很大，請輸出答案模 10?+7 的結果。
輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積。
接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值。
輸出格式
輸出一個整數，表示方案數 模 10?+7 的結果。
數據范圍
0<N,V≤1000
0<vi,wi≤1000
輸入樣例
4 5
1 2
2 4
3 4
4 6
輸出樣例
2
法一：根據體積恰好為j時價值的大小來更新方案數
1 #include<iostream> 2 #include<climits> 3 #include<algorithm> 4 using namespace std; 5 const int n = 1001; 6 int N, V, v, w, f[n], g[n];//f[j]、g[j]分別表示體積恰好為j時的最大價值、方案數 7 int mod = 1000000007; 8 int main() { 9 cin >> N >> V; 10 g[0] = 1; 11 for (int i = 1; i <= V; ++i) 12 f[i] = INT_MIN; //除0以外，全部設為負無窮，確保都是從f[0]傳遞過去的 13 for (int i = 0; i < N; ++i) { 14 cin >> v >> w; 15 for (int j = V; j >= v; --j) { 16 int s = 0, t = max(f[j], f[j - v] + w); 17 if (t == f[j]) 18 s += g[j]; //添加不更新的方案 19 if (t == f[j - v] + w) 20 s += g[j - v]; //添加更新的方案 21 if (s >= mod) 22 s -= mod; 23 f[j] = t; 24 g[j] = s; 25 } 26 } 27 int maxn = 0, res = 0; 28 for (int i = 0; i <= V; ++i) 29 maxn = max(maxn, f[i]); //獲取最大價值 30 for (int i = 0; i <= V; ++i) 31 if (maxn == f[i]) { //等于最大價值的方案都添加 32 res += g[i]; 33 if (res >= mod) 34 res -= mod; 35 } 36 cout << res; 37 }
法二：根據體積最大為j時價值的大小來更新方案數
1 #include<iostream> 2 #include<climits> 3 #include<algorithm> 4 using namespace std; 5 const int n = 1001; 6 int N, V, v, w, f[n], g[n];//f[j]、g[j]分別表示體積最大為j時的最大價值、方案數 7 int mod = 1000000007; 8 int main() { 9 for (int i = 0; i < n; ++i) 10 g[i] = 1; //默認體積最大為i時方案數為1 11 cin >> N >> V; 12 for (int i = 0; i < N; ++i) { 13 cin >> v >> w; 14 for (int j = V; j >= v; --j) { 15 if (f[j] < f[j - v] + w) { 16 f[j] = f[j - v] + w; 17 g[j] = g[j - v]; //使用新方案時更新方案數為g[j-v]的方案數 18 } 19 else if (f[j] == f[j - v] + w) 20 g[j] = (g[j] + g[j - v]) % mod; //原方案數加跟新方案數 21 //使用原方案時方案數不變，故不作操作。 22 } 23 } 24 cout << g[V]; 25 }
浙公網安備 33010602011771號