$$\color{Red}{完全背包问题:三种语言+原版和滚动数组优化}$$

我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

有 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

输出样例：

10

方法一：朴素版代码思想

与01背包问题类似，但是我们在第二重循环对状态方程赋值时，max()内应该是能放下1-k个（k即最多个数）的表达式
为了解决写出如此庞杂的表达式，可以直接调用一层for循环

1.具体代码

此方法复杂度太高，极易TLE

for(int i = 1 ; i <= n ;i ++)
    for(int j = 0 ; j <= m ;j ++)
        for(int k = 0 ; k * v[i] <= j ; k ++)
            f[i][j] = max(f[i][j], f[i-1][j-k * v[i]]+k * w[i]);

为什么不是f[i][j] = max(f[i-1][j], f[i-1][j-k * v[i]]+k * w[i]);
当k等于0时，即是f[i-1][j]
同时在k次循环当中，写入自己是完成对k的所有取值的不断刷新，如果改完刷新f[i][j]的值每次只和f[i-1][j]比较

方法二：精妙的错位相减

我们不妨分析一下此时如何优化最内层的循环

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-v] + w即为第一个式子除第一项右边的部分,故由此可得：
f[i][j] = max( f[i-1][j], f[i,j-v] + w )

1.算法优化和细节

• 不难发现，此式和01背包极其类似:f[i][j] = max(f[i-1][j], f[i-1][j - v[i]] + w[i])
• 那么这个不同点是怎么来的？

完全背包的f[i,j-v] + w是由错位相减所得，本质是从f[i][j]的第二项展开和原式裂项错位相减所得
01背包的f[i-1][j - v[i]] + w[i]是由预留空间给v[i]，从而算出f[i][j]使用i这个物品的价值量
因此他们两个一个代表着用当前背包状态出发，一个代表着使用上一状态去预留计算

• 优化到二维，为什么非得加入一部f[i][j] = f[i-1][j]再去判断条件？

dp[i-1][j]即不放第i件物品到背包，这个情况一定存在，但是未必还能放下一件，如果直接去求max，就会产生边界错误

for(int j = 0; j <= m; j ++ ){
            dp[i][j] = dp[i - 1][j];
            if(j >= v)
                dp[i][j] = max(dp[i][j], dp[i][j - v] + w);
        }

这两个均可以AC的代码可以帮助我们了解实际出现的边界情况

for(int j = 0; j <= m; j ++ ){
    if(j < v)   dp[i][j] = dp[i-1][j];
    else
        dp[i][j] = max(dp[i-1][j], dp[i][j - v] + w);
}

1.二维java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static int n, m;
    static int[][] f = new int[N][N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] str1 = br.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        for (int i = 1; i <= n; i++) {
            String[] str2 = br.readLine().split(" ");
            int v = Integer.parseInt(str2[0]);
            int w = Integer.parseInt(str2[1]);
            for (int j = 1; j <= m; j++) {
                f[i][j] = f[i-1][j];
                if (j >= v)
                    f[i][j] = Math.max(f[i][j], f[i][j - v] + w);
            }
        }
        System.out.println(f[n][m]);
    }
}

2.二维python3代码

N = 1010
v = [0] * N
w = [0] * N
f = [[0] * N for i in range(N)]

n, m = map(int, input().split())
for i in range(1, n+1):
    v[i], w[i] = map(int, input().split())

for i in range(1, n+1):
    for j in range(m+1):
        if j >= v[i]:
            f[i][j] = max(f[i-1][j], f[i][j - v[i]] + w[i])
        else:
            f[i][j] = f[i-1][j]

print(f[n][m])

最终进一步优化到一维的区别和理由

由01背包的最终优化到1维，完全背包也可以由此进行优化

1.01背包的最终代码

for(int i=1; i<=n; i++)//挑选物品数
    for(int j=m; j>=v[i]; j--)//正序会污染我们本想取的f[i-1][j]
        f[j] = max(f[j], f[j - v[i]] + w[i]);

2.完全背包的最终代码

for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//为什么这里采用了正序？
            f[j] = max(f[j], f[j - v[i]] + w[i]);

完全背包的正序由我们对两个算法的不同点总结可知，完全背包利用的就是当前状态
看似01背包提前将更小背包的状态方程值刷新的污染,恰好在完全背包可以直接利用进行计算错位相减的右值

2.具体代码

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static int n, m;
    static int[] f = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] str1 = br.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        for (int i = 1; i <= n; i++) {
            String[] str2 = br.readLine().split(" ");
            int v = Integer.parseInt(str2[0]);
            int w = Integer.parseInt(str2[1]);
            for (int j = v; j <= m; j++) 
                f[j] = Math.max(f[j], f[j - v] + w);
        }
        System.out.println(f[m]);
    }
}

python3

N = 1010
v = [0] * N
w = [0] * N
f = [0] * N

n, m = map(int, input().split())
for i in range(1, n+1):
    v[i], w[i] = map(int, input().split())

for i in range(1, n+1):
    for j in range(v[i], m+1):
            f[j] = max(f[j], f[j - v[i]] + w[i])

print(f[m])

C++

#include <iostream>
using namespace std;

const int N = 1010;
int w[N], v[N], dp[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)  scanf("%d%d", &v[i], &w[i]);

    for(int i=1; i<=n; i++)
        for(int j=v[i]; j<=m; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[m] << endl;
    return 0;
}