完全背包问题

有 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:
10

题解思路 DP

完全背包问题和01背包非常相似，差别仅在于每个物品可以无限次的使用。如同01背包一样，我们定义

f[i][j] 表示从前i个物品中，选择总体积不超过j的所有物品集合，我们求解的目标是这个集合的最大价值。

那么

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

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

1.当我们选择1个物品i时

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

2.当我们选择2个物品i时

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

k.当我们选择k个物品i时

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

......

综上，只要满足 k * v[i] <= j，我们从0开始遍历k，可得

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

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

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;
    scanf("%d %d", &n, &m);

    int v[N] = {0};
    int w[N] = {0};
    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) {
            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]);
            }
        }
    }

    printf("%d\n", f[n][m]);
    return 0;
}

代码时间优化

这显然是一个$O(n^3)$的算法，会被OJ判TLE的。我们再次注意观察 f[i][j] 的递推方程, 并思考对应的 f[i][j - v[i]] 的递推方程

1. f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i], ..., f[i - 1][j - k * v[i]] + k * w[i]) 

2. f[i][j - v[i]] = max(      f[i - 1][j - v[i]],        f[i - 1][j - 2 * v[i]] + 1 * w[i], ..., f[i - 1][j - k * v[i]] + (k - 1) * w[i]) 

不难发现，将方程2和方程1有很多相似的项(在代码中对齐的各项之差只有一个w[i])，将方程2整体代入方程1，可得

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

这是一个和k无关的方程，故我们可以将遍历k的循环删除掉，将算法的时间复杂度优化为$O(n^2)$

#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;
    scanf("%d %d", &n, &m);

    int v[N] = {0};
    int w[N] = {0};
    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][j - v[i]] + w[i]);
        }
    }

    printf("%d\n", f[n][m]);
    return 0;
}

代码空间优化

再次观察上述时间复杂度为$O(n^2)$的算法，和空间复杂度为O(nm)的01背包问题的代码已经很相似了，我们可以使用同样的优化方法，将空间复杂度优化为O(m)。

#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 = v[i]; j <= m; ++j) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    printf("%d\n", f[m]);
    return 0;
}

和01背包问题的最终代码，只是在j的遍历方向上不同，其他都一样，amazing！