背包问题求方案数（动态规划）

本文主要是介绍背包问题求方案数（动态规划），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

这篇关于背包问题求方案数（动态规划）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！