• 欢迎光临~

01背包问题

开发技术 开发技术 2022-10-05 次浏览

问题描述

01背包问题
(N)件物品和一个容量是(V)的背包,每件物品只能使用一次。

(i)件物品的体积是(v_i),价值是(w_i),求解将哪些物品装入背包,可使这些物品总体积不超过背包容量,并且总价值最大。

解题思路

动态规划的经典例题,首先考虑dp[i][j]的含义,这里i表示只考虑前i个物品(i(1sim N)),dp[i][j]表示总体积为j的情况下,考虑前i个物品时,背包里的物品的最大价值。

可以分成两种情况考虑dp[i][j]的递推关系:

  • i个物品不在背包中时,dp[i][j] = dp[i - 1][j]
    • 此时只有前i - 1个物品,背包中物品体积仍为j
  • i个物品在背包中时,dp[i][j] = dp[i - 1][j - v[i]] + w[i]
    • i - 1个物品的体积为j - v[i]

初始化,显然dp[0][0] = 0

根据递推关系和初始化条件写for循环遍历即可。

代码

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int N = 1010; // 体积不超过1000, 物品件数也不超过1000

int main() {
    int n, m; // n为物品数量,m为背包体积
    cin >> n >> m;
    int dp[N][N] = {0};
    int v[N] = {0}; // 体积
    int w[N] = {0}; // 价值
    for (int i = 1; i <=n; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) // 当前总体积肯定不能小于v[i],如果小于的话,第i个物品不能放
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    // int res = 0;
    // for (int j = 1; j <=m; j++) {
    //     res = max(res, dp[n][j]); // 不需要遍历,直接输出dp[n][m]即可
    // }
    cout << dp[n][m] << endl;
    return 0;
}

优化

分析上面的代码,实际上dp[i][j]递推时只会用到dp[i - 1][j],而不会用到dp[i - 2][j], dp[i - 3][j]等,因此dp数组实际上只需要一维即可,索引为当前总体积。

那么,是否可以直接写成

for (int i = 1; i < n; i++) {
    for (int j = 1; j <= m; j++)
        if (j >= v[i])
            // 这里的max实际上是
            // max(dp[i][j], dp[i][j - v[i]] + w[i])
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);  
}

不可以!原因已在上面的代码里的注释中给出,应该是max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])才对。

正确的写法应该是:

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--)
        // 因为dp[j], dp[j - v[i]]只在上一次的i循环中才被赋值了,
        // 所以这里用的实际上是dp[i - 1][j - v[i]]
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]); 
}

如果dp[0] = 0, dp[i] = -INF,那么状态只能从dp[0]转移过来,可以求解总体积恰为(V)的情况。

优化后的完整代码:

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int N = 1010; // 体积不超过1000, 物品件数也不超过1000

int main() {
    int n, m; // n为物品数量,m为背包体积
    cin >> n >> m;
    int dp[N] = {0};
    int v[N] = {0}; // 体积
    int w[N] = {0}; // 价值
    for (int i = 1; i <=n; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
                // 当前总体积肯定不能小于v[i],如果小于的话,第i个物品不能放
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    // int res = 0;
    // for (int j = 1; j <=m; j++) {
    //     res = max(res, dp[n][j]); // 不需要遍历,直接输出dp[n][m]即可
    // }
    cout << dp[m] << endl;
    return 0;
}

例题

  • 416.分割等和子集
    • 416.分割等和子集-题解
  • 1049.最后一块石头的重量II
    • 1049.最后一块石头的重量II-题解
  • 494.目标和
    • 494.目标和-题解
  • 474.一和零
    • 474.一和零-题解
程序员灯塔
转载请注明原文链接:01背包问题
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com