有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 最优选法的方案数。注意答案可能很大,请输出答案模 10^9+7的结果。
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出一个整数,表示 方案数 模 10^9+7 的结果。
0<N,V≤1000
0<vi,wi≤1000
4 5 1 2 2 4 3 4 4 6
2
基于01背包问题
1.未放入i物品的最大值(X) > 放入i物品的最大值(Y) => 即方案数 = X的方案数
2.未放入i物品的最大值(X) < 放入i物品的最大值(Y) =>即方案数 =Y的方案数
3.未放入i物品的最大值(X)==放入i物品的最大值(Y) => 即方案数 = X的方案数+Y的方案数
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 5 using namespace std; 6 7 constexpr int N = 1010; 8 constexpr int MOD = 1e9 + 7; 9 int main() { 10 int n = 0; // 物品数量 11 int v = 0; // 背包容量 12 13 std::cin >> n >> v; 14 vector<int> dp(N, 0); // 背包容量为j时能装入物品的最大价值 15 vector<int> solutions(N, 0); // 背包容量为j时最优选法的方案数 16 solutions[0] = 1; // 容量为0时的最大价值的方案数为1,就是一个都不选 17 /* 18 * 思路: 19 * 1.未放入i物品的最大值(X) > 放入i物品的最大值(Y) => 即方案数 = X的方案数 20 * 2.未放入i物品的最大值(X) < 放入i物品的最大值(Y) =>即方案数 =Y的方案数 21 * 3.未放入i物品的最大值(X)==放入i物品的最大值(Y) => 即方案数 = X的方案数+Y的方案数 22 */ 23 for (int i = 1; i <= n; i++) { 24 int volume = 0; 25 int weight = 0; 26 std::cin >> volume >> weight; 27 for (int j = v; j >= volume; j--) { 28 int maxv = max(dp[j], dp[j - volume] + weight); 29 int cnt = 0; 30 // 1、未放入i物品的最大值(X) > 放入i物品的最大值(Y) => 即方案数 = X的方案数 31 if (maxv == dp[j]) { // 第j个物品不选 32 cnt += solutions[j]; 33 } 34 // 2、未放入i物品的最大值(X) < 放入i物品的最大值(Y) =>即方案数 =Y的方案数 35 if (maxv == dp[j - volume] + weight) { // 第j个物品选择 36 cnt += solutions[j - volume]; 37 } 38 // 3、未放入i物品的最大值(X)==放入i物品的最大值(Y) => 即方案数 = X的方案数+Y的方案数 39 solutions[j] = cnt % MOD; 40 // 容量为j时能装入物品的最大价值 41 dp[j] = maxv; 42 } 43 } 44 int maxValue = -1; 45 for (int j = 0; j <= v; j++) { 46 maxValue = max(maxValue, dp[j]); 47 } 48 int sumOfSolutions = 0; 49 for (int j = 0; j <= v; j++) { 50 if (dp[j] == maxValue) { 51 sumOfSolutions = (sumOfSolutions + solutions[j]) % MOD; 52 } 53 } 54 std::cout << sumOfSolutions << endl; 55 return 0; 56 }