题目

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wj。

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

输入格式

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

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

输出格式

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

数据范围

0 < N, V ≤ 10000 < N, V ≤ 1000
0 < vi, wi ≤ 1000

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例

1
8

二维动态规划

分析

01背包特点：每个物品只能使用一次

状态转移方程： 定义dp[i][j]：前 i 个物品，背包容量为 j 时的最有解

  • 如果不装第 i 件物品，那么问题就转化为前 i − 1 件物品放入容量为 j 的背包中的最大价值

    即 dp[i][j] = dp[i - 1][j]

  • 如果装第 i 件物品，那么问题就转化为前 i - 1 件物品放入剩下容量为 j - v[i] 的背包中的最大价值

    即 dp[i][j] = dp[i - 1][j - v[i]] + w[i]

总的方程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N], w[N];
int dp[N][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 = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i])	// 确保背包容量足够
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}

一维动态规划

分析

即二维动态规划的空间优化

状态转移方程：（ j 采取逆序的方式）

​ dp[j] = max(dp[j], dp[j - v[i]] + w[i])

其实两种做法，实现的思想是一样的，只不过一维数组更省空间，下面具体说说，为什么可以用一维数组来代替,而且要采取逆序的方式。

为什么可以用一维数组代替

根据二维状态转移方程，dp[i]这一层的更新只用到了dp[i - 1]这一层的数据，所以可以用滚动数组来优化。

对于外层循环中的每一个 i 值，其实都是不需要记录的，在第 i 次循环时，所有的dp[0…v]都还未更新时，dp[j]还记录着前 i - 1 个物品在容量为 j 时的最大价值，这样就相当于还记录着dp[i-1][j]和dp[i-1][j-v[i]]+w[i]。

为什么要逆序

举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
假如枚举到：i = 3, j = 8, v[3] = 5, w[3] = 1

二维：dp[3][8] = max(dp[2][8], dp[2][3] + w[3])   此时的dp[2][8]和dp[2][3]都是上一轮的状态值

一维：dp[8] = max(dp[8], dp[3] + w[3])      我们要保证dp[8]和dp[3]都是上一轮的状态值

按照逆序的顺序，一维dp数组的更新顺序为：dp[8], dp[7], dp[6], ... , dp[3]

也就是说，在本轮更新的值，不会影响本轮中其他未更新的值！较小的index对应的状态是上一轮的状态值！

如果按照顺序进行更新，dp[3] = max(dp[3], dp[0] + w[0])，对dp[3]的状态进行了更新，
那么在更新dp[8]时，用到的dp[3]就不是上一轮的状态了，不满足动态规划的要求。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N], w[N];
int 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 = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    printf("%d", dp[m]);
    return 0;
}