首页 程序设计 动态规划 背包问题

# 题目大意

有 nn 种物品和一个容量是 vv 的背包，每种物品都有无限件
第 ii 种物品的体积是 viv_i，价值是 wiw_i
问：你放进背包的最大价值是多少

# 数据范围

  • 0<N,V≤10000 < N, V \le 1000
  • 0<vi,wi≤10000 < v_i, w_i \le 1000

# 思路

显然可以借鉴 0101 背包的思路， dp[i][j] 表示选到第 ii 个物品，背包容量为 jj 时的最大容量
那么，完全背包就是在 0101 背包的基础上，多增加一层循环，枚举需要多少个

C++
1
2
3
4
5
6
7
8
9
10
11
12
void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> 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++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);

    cout << dp[n][m] << endl;
}

这个代码仅限思路理解，会 TLETLE，需进行优化，观察有
C++
1
2
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][j - v[i]] = max(             f[i - 1][j - v[i]],        f[i - 1][j - 2 * v[i]] + w[i], ...)

推导有
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]
由此可以将三维优化到二维
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> 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][j - v[i]] + w[i]);
        }

    cout << dp[n][m] << endl;
}

观察有，更新的时候，用到了同层的 dp[i][j - v[i]] 和 上一层的 dp[i][j] ，由此优化到一维
因为用到了同层的，所以应该从小的 v[i] 遍历到大的 m
C++
1
2
3
4
5
6
7
8
9
10
11
void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> 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;
}