$$\color{Red}{01背包问题:二维费用的背包问题}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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


每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0 < N ≤ 1000

0 < V , M ≤ 100

0 < vi , mi ≤ 100

0 < wi ≤ 1000

输入样例：

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例：

8

思路

比起01背包只是多了一个费用：重量，只需要进行多一层循环，重量的判断和转移即可，滚动数组优化显然也要用到i-1层的状态，需要倒序遍历

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010, n, m, Weight;
    static int[][] f = new int[N][N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String [] str1 = br.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        Weight = Integer.parseInt(str1[2]);

        for (int i = 1; i <= n; i++) {
            String [] str2 = br.readLine().split(" ");
            int v = Integer.parseInt(str2[0]);
            int x = Integer.parseInt(str2[1]);
            int w = Integer.parseInt(str2[2]);
            for (int j = m; j >= v; j--) {
                for (int k = Weight; k >= x; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - v][k - x] + w);
                }
            }
        }
        System.out.println(f[m][Weight]);
    }
}

python3

f = [[0] * 110 for i in range(110)]
N, V, M = map(int, input().split())

for i in range(N):
    v, m, w = map(int, input().split())
    for j in range(V, v-1, -1):
        for k in range(M, m-1, -1):
            f[j][k] = max(f[j][k], f[j - v][k - m] + w)

print(f[V][M])