0003

3. 完全背包问题

题目

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。

第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 种物品的体积和价值。

输出格式

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

数据范围

$0 \lt N, V \le 1000$

$0 \lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

题解

前置题目：0002

前置知识：01背包

本题知识：动态规划-背包问题

题目分析

本题比01背包问题多的一个条件是选择每个物品时的数量不限，而不只是 0 个或 1 个，但所求的仍是拥有最大价值的选择方法。

题目的解：从前 N 件物品中选择任意件物品，每件物品选择任意个，使得总体积小于等于 V，在这个集合中的具有最大价值的元素

对题目的解进行分解，因为总容量有限，故不妨设在不超过容量限制条件的第 N 件物品最多选择 k 个，分解情况如下：

• 第 N 件物品选择 0 个
• 第 N 件物品选择 1 个
• 第 N 件物品选择 2 个
• 第 N 件物品选择 ... 个
• 第 N 件物品选择 k-1 个
• 第 N 件物品选择 k 个

以上 k+1 种情况组成了全部的集合，题目的解即是其中具有最大价值的选择

思路转换，对从前 N 件物品中选择的最大价值求解比较困难，需要转换成对从前 N-1 件物品中选择的最大价值求解，比如下面这个例子

在对第 N 件物品选择 2 个的情况下的最大价值 == （不选择第 N 件物品，总体积小于等于最大体积 V-2*N 物品的体积）这种选法的最大价值 + 2*第 N 件物品的价值

这样就很好的从前 N 件物品中选择转化成了从前 N-1 件物品中选择

具体实现

设集合(i, j)表示从前 i 个物品中选择，每件物品可选择任意个，且总体积小于等于 j

设函数f表示在集合中选择最大价值

f(N, V)是题目的解

方法一：三重循环

// 直接对分解的 k+1 种情况朴素的求解出其中最大的值
for i := 1; i <= n; i++ {
    for j := 0; j <= m; j++ {
        for k := 0; k*v[i] <= j; k++ {
            if f[i-1][j-v[i]*k]+w[i]*k > f[i][j] {
                f[i][j] = f[i-1][j-v[i]*k] + w[i]*k
            }
        }
    }
}

方法二：三重循环优化成二重循环

// 伪代码思路如下
f(i, j ) = Max( f(i-1,j) , f(i-1,j-v)+w ,  f(i-1,j-2*v)+2*w , f(i-1,j-3*v)+3*w , .....)
f(i, j-v)= Max(            f(i-1,j-v)   ,  f(i-1,j-2*v) + w , f(i-1,j-3*v)+2*w , .....)
    
// 通过函数递推不难得出
f(i, j) = Max(f(i, j-v)+w ,f(i-1, j))

for i := 1; i <= n; i++ {
    for j := 0; j <= m; j++ {
        f[i][j] = f[i-1][j]
        if j-v[i] >= 0 && f[i][j-v[i]]+w[i] > f[i][j] {
            f[i][j] = f[i][j-v[i]] + w[i]
        }
    }
}

方法三：二维数组优化成一维数组

故技重施，通过滚动数组降低维度

不过要注意和01背包问题的区别，此时的递推式中的f(i, j-v)即g(j-v)是在第 i 层计算得到的，

所以此时循环从小到大时计算到g(j)所用到的g(j-v)已经是在第 i 层计算过的，刚好满足要求。

for i := 1; i <= n; i++ {
    for j := v[i]; j <= m; j++ {
        if g[j-v[i]]+w[i] > g[j] {
            g[j] = g[j-v[i]] + w[i]
        }
    }
}