背包九讲之二维费用的背包问题

2021-03-24

[toc]

说明:

本文所讲内容摘录自崔添翼:背包九讲,并对其中的数学内容和一些较为复杂的内容进行了删减,增加了基础的例题,只是面向初学者或者不需要深入理解背包及其衍生问题的读者,如果有能力并且有意愿加深理解,本文可能会对您形成误导,请移步崔添翼:背包九讲.

二维费用的背包问题

题目

二维费用的背包问题是指：对于每件物品，只能使用一次，但是其具有两种不同的费用，选择这件物品必须同时付出这两种费用。对于每种费用都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设第 i 件物品所需的两种费用分别为 $C_i$ 和 $D_i$。两种费用可付出的最大值（也即两种背包容量）分别为 V 和 U。物品的价值为 $W_i$。

基本思路

费用加了一维，只需状态也加一维即可。设 $F[i, v, u]$ 表示前 i 件物品付出两种费用分别为 $v$ 和 $u$ 时可获得的最大价值。
$$
F[i, v, u] = max\left{F[i − 1, v, u], F[i − 1, v −C_i, u −D_i] +W_i\right}
$$

上述问题的伪代码

int N, V, M;
// ccw[i][0]是放第i件物品消耗的费用1,ccw[i][1]是第i件物品的费用2,ccw[i][2]是放第i件物品的收益价值,其中i从1开始
int[][] ccw = new int[N + 1][3];
int dp[][][] = new int[N + 1][V + 1][M + 1];
dp[0][0][0] = 0;
for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= V; j++) {
        for (int k = 0; k <= M; k++) {
            if (ccw[i][0] <= j && ccw[i][1] <= k) {
                dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - cv[i][0]][k - ccw[i][1]] + ccw[i][2]);
            } else {
                dp[i][j][k] = dp[i - 1][j][k];
            }
        }
    }
}
return dp[N][V][M];

注意❗: 外层i枚举物品的数量,内层j枚举背包可以容纳的容量，最内层k枚举背包可以承载的重量

注意❗❗❗: 转移方程为dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i - 1][j - cv[i][0]][k-cv[i][1]] + cv[i][2]) max函数里面是dp[i][j]和dp[i - 1][j - k * cv[i][0]] + k * cv[i][1]这两项, 切记!切记!

一个简单有效的优化

略🚮🤐(太菜了,慢慢来)

相关题目练习

题目URL

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。 体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 $v_i,m_i,w_i$，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式

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

数据范围

$0<N≤10000<N≤1000$

$0<V,M≤1000<V,M≤100$

$0<vi,m_i≤1000<v_i,m_i≤100$

$0<w_i≤10000<w_i≤1000$

输入样例

输出样例：

题目解法

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 物品的数量
        int N = sc.nextInt();
        // 背包的容量
        int V = sc.nextInt();
        // 背包可承载的重量
        int M = sc.nextInt();

        // 每个物品的体积和价值
        int[][] vmw = new int[N + 1][3];
        for (int i = 1; i <= N; i++) {
            // 体积
            vmw[i][0] = sc.nextInt();
            // 重量
            vmw[i][1] = sc.nextInt();
            // 价值
            vmw[i][2] = sc.nextInt();

        }

        int dp[][][] = new int[N + 1][V + 1][M + 1];
        // 不要求完全装满背包,初始化全设置为0,因为java默认int数组为0所以象征性的初始化第一个
        dp[0][0][0] = 0;

        // 枚举第i件物品
        for (int i = 1; i <= N; i++) {
            // 枚举背包的容量j
            for (int j = 0; j <= V; j++) {
                // 枚举背包可以承载的重量
                for (int k = 0; k <= M; k++) {
                    // 如果体积和重量可以同时满足要求，那么可以选择加入或者不加入当前的物品
                    if (vmw[i][0] <= j && vmw[i][1] <= k) {
                        // 不加入当前的物品,那么问题转化成i-1件物品装到可容纳体积为j可承载重量为k的背包里的子问题:dp[i - 1][j][k]
                        // 如果加入当前的物品,收益加了vw[i][2],那么问题转化成i-1件物品装到可容纳体积为j-vw[i][0],可承载重量为k-vw[i][1]的背包的子问题
                        // 要想使背包最后的收益更高,需要选择两个子问题的最大价值
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - vmw[i][0]][k - vmw[i][1]] + vmw[i][2]);
                    } else {
                        // 如果体积或者重量不能满足要求,那么只能转化成i-1件物品装到可容纳体积为j可承载重量为k的背包里的子问题:dp[i - 1][j][k]
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        // 返回N件物品,背包容量为V,可承载重量M的情况下装入的最大价值
        System.out.println(dp[N][V][M]);
    }
}

参考文献

崔添翼:背包九讲