背包问题

2020-05-03

参考博客：https://www.cnblogs.com/jbelial/articles/2116074.html

01背包问题

01背包问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

用子问题定义状态：即$f[i][v]$表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：$f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i])$。

“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。

如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是$f [i-1][v-c[i]]$再加上通过放入第i件物品获得的价值w[i]。


// 根据公式得到的解法
int func1(int n, int m) {
    for (int i = 1;i <= n;i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j]; // 不选第i个商品
            // 选了第i个商品，体积小于当前总体积
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    int res = 0;
    for (int i = 0; i <= m; i++) res=max(res, f[n][i]);
    return res;
}
int func2(int n, int m) {
    // 优化空间复杂度
    for (int i = 1;i <= n;i++) {
        for (int j = m; j >= v[i]; j--) {
            // if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            // 计算f[i] 的时候，需要用到f[i-1]的状态
            // 顺序遍历时，f[j-v[i]]已经在之前计算过了，后续都是多次使用同一商品计算；
            // 逆序遍历时，f[j-v[i]]的状态绝对没有被计算过,一定是f[i-1]的状态
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    // 如果要计算恰好V为m的价值，则在初始化时 f[0]=0。其余f[i]=-INF
    // 保证所有状态都是从f[0]转移过来
    int res = f[m];
    return res;
}

完全背包问题

完全背包问题

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

用子问题定义状态：即$f[i][v]$表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：$f[i][v]=max(f[i-1][v-kc[i]]+kw[i]|0<=k*c[i]<= v)$。

int completePack(int n, int m) {
    // f[i] 表示总体积为i的情况下，最大价值是多少
    // res = max(f[0...m])
    /*
     for (int j = m; j >= v[i]; j--) {
        for (int k = 0; k*v[i]<=j;k++) {
            // 此时计算的都不包含第i个物品，枚举选择k个,更新每一种的状态
            f[j] = max(f[j], f[j - k*v[i]] + k*w[i]);
        }
    }
     */
    // 优化空间复杂度
    for (int i = 1;i <= n;i++) {
        // 逆序遍历，每个物品只使用一次
        // 顺序遍历，在计算f[v[i]...m]时，f已经更新了，使用多个v[i]时的价值状态
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    int res = f[m];
    return res;
}

多重背包问题 I

多重背包问题

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

用子问题定义状态：即$f[i][v]$表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：$f[i][v]=max(f[i-1][v-kc[i]]+ kw[i]|0<=k<=n[i])$。

int MultiPack(int n, int m) {
    // 多重背包问题
    // 每个商品可以选s[i]个
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= v[i];j--) {
            for (int k = 0;k<=s[i] && k*v[i]<=j;k++) {
                f[j] = max(f[j], f[j-k*v[i]] + k*w[i]);
            }
        }
    }
}