3 完全背包问题

﹏ヽ暗。殇╰゛Y 2022-09-11 03:13 145阅读 0赞

**1. 问题描述：**

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

**输入格式**

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 种物品的体积和价值。

**输出格式**

输出一个整数，表示最大价值。

**数据范围**

0 < N，V ≤ 1000  
0 < vi，wi ≤ 1000

**输入样例**

4 5  
1 2  
2 4  
3 4  
4 5

**输出样例：**

来源：[https://www.acwing.com/problem/content/3/][https_www.acwing.com_problem_content_3]

**2. 思路分析：**

**完全背包问题**属于经典的背包问题，对于每一个物品可以选择无限次（在背包容量允许的前提下），属于动态规划中一大类的题目，对于动态规划的题目一般有两个步骤：① 状态表示 ② 状态计算；一开始的时候我们可以定义一个二维数组或者二维列表，其中dp\[i\]\[j\]表示从前i个物品中选总体积不超过j的最大的价值。怎么样进行状态的计算呢？状态计算对应集合的划分，一般是找最后一个不同点，我们可以根据最后一个物品选择的次数划分为k个子集，经过推导可以得到状态转移方程为：dp\[i\]\[j\] = max(dp\[i - 1\]\[j\]，dp\[i\]\[j - v\[i\]\] + w\[i\])，可以参照下图中的推导过程，其实我们可以将二维的数组优化为一维数组，只要做等价的变形即可完成优化，我们可以参照状态转移方程，可以发现dp\[i - 1\]\[j\]其实使用到了上一层i - 1的状态，而dp\[i\]\[j - v\]使用到的是当前这一层的状态。进入到第二层循环的时候所有的状态j对应的都是上一层i - 1的状态（循环变量j是按顺序遍历的），而进入循环之后j - v小于j所以j - v对应的状态是当前这一层i计算的结果（循环到当前的j之后dp\[j - v\]已经在当前这一层循环中计算出结果了），所以直接去掉一维就可以完成等价变形，这里需要与零一背包优化的思路做一下区分。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

if __name__ == '__main__':
        n, V = map(int, input().split())
        dp = [0] * (V + 1)
        for i in range(n):
            v, w = map(int, input().split())
            for j in range(v, V + 1):
                dp[j] = max(dp[j], dp[j - v] + w)
        print(dp[V])

[https_www.acwing.com_problem_content_3]: https://www.acwing.com/problem/content/3/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b853ac3b846e4353b25f4657ea40697b.png