11 背包问题求方案数

比眉伴天荒 2022-09-11 10:14 115阅读 0赞

**1. 问题描述：**

有 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  
来源：[https://www.acwing.com/problem/content/description/11/][https_www.acwing.com_problem_content_description_11]

**2. 思路分析：**

这道题目求方案数目与之前[1023][]买书的题求解方案数目是不一样的，这里需要求解在不超过背包容量的前提下能够获得最大价值的方案数目，所以多了最大价值的限制，分析题目可以知道这道题目属于经典的**零一背包问题**，因为有了价值的限制，一个dp数组只能够记录最大价值，所以我们还需要声明一个数组g来记录对应体积的方案数目（这样dp数组中记录的就是最大价值，而g数组中记录的就是对应体积的方案数目），为了方便后面计算方案数目我们在状态定义的时候定义的不是不超过背包容量能够获得的最大价值，而是体积恰好为j能够获得的最大价值（后面可以枚举出体积取到多少的时候可以获得最大价值）；一般题目中[体积的限制][Link 1]有三种，这里定义的是"恰好"而且求解的是最大值，所以我们在初始化的时候将所有元素置为最小值，并且只有dp\[0\]是满足要求的，二维数组对应的dp和g数组的状态表示分别为：dp\[i\]\[j\]表示只从前i个物品中选，体积恰好为j能够获得的最大价值，g\[i\]\[j\]表示只从前i个物品中选，且体积恰好为j的方案数目，在计算当前g\[i\]\[j\]的方案数目的时候需要先判断一下，判断属于哪一种情况取到的最大值，主要分为三种情况：

*  不选当前的物品得到的最大价值，s = g\[i - 1\]\[j\]
 *  选当前的物品得到的最大价值，s = g\[i - 1\]\[j - v\]
 *  两种情况都可以得到当前的最大价值那么则s应该加上两种情况对应的方案数目，最后令g\[i\]\[j\] = s即可

因为定义的是体积恰好为j的方案数目，所以最终的dp\[n\]\[V\]不一定是答案，我们需要枚举出获得最大价值的体积（枚举一下所有体积求解最大值即可），然后累加所有最大价值对应体积的方案数目即可。

**3. 代码如下：**

if __name__ == "__main__":
        n, V = map(int, input().split())
        INF = 10 ** 9 + 7
        dp = [-INF] * (V + 1)
        g = [0] * (V + 1)
        # 这里在状态定义的是恰好装满背包的最大价值所以初始化的时候将值全部置为最小值只有dp[0]是合法的为0
        dp[0] = 0
        g[0] = 1
        mod = 10 ** 9 + 7
        for i in range(n):
            v, w = map(int, input().split())
            for j in range(V, v - 1, -1):
                s = 0
                maxv = max(dp[j], dp[j - v] + w)
                if maxv == dp[j]: s = g[j]
                if maxv == dp[j - v] + w: s = (s + g[j - v]) % mod
                dp[j] = maxv
                g[j] = s
        # 接下来求解最大值对应的体积
        res = 0
        for i in range(1, V + 1):
            if dp[i] > dp[res]: res = i
        s = 0
        # 累加方案判断dp数组中能够取到最大值对应的体积, 而g[i]存的就是体积恰好为i的方案数目
        for i in range(V + 1):
            if dp[i] == dp[res]: s = (s + g[i]) % mod
        print(s)

[https_www.acwing.com_problem_content_description_11]: https://www.acwing.com/problem/content/description/11/
[1023]: https://blog.csdn.net/qq_39445165/article/details/120229358
[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120233950