01背包问题

01背包问题

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

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

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

输入格式

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

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

输出格式

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

数据范围

0 < N, V <= 1000

0 < vi, wi <= 1000

Example 1:

Input:
4 5

1 2
2 4
3 4
4 5
Output:
8

题解思路 DP

我们定义

fi 表示从前i个物品中，选择总体积不超过j的所有物品集合的最大价值

那么

1.当我们不选择物品i时,

f[i][j] = f[i - 1][j]

2.当我们选择物品i时

f[i][j] = f[i - 1][j - v[i]] + w[i]

综上可得，

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

那么，我们最终要求得的问题最终解即fn。
根据状态计算，写出代码。

code

#include <stdio.h>
#include <algorithm>
using namespace std;

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

代码优化

观察上述代码，我们不难发现，第一维数组f[i]，只和f[i -1]相关，在遍历i的过程中，我们必先会求得f[i - 1]，故可以做等价变换，将i这个维度去掉，简化代码如下

#include <stdio.h>
#include <algorithm>
using namespace std;

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