有 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 }