二维费用的背包问题（背包有体积和重量两个限制）_二维费用背包题目描述有 n 件物品和一个容量是 v 的背包,背包能承受的最大重量是

题目描述：有 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

分析：每个物品只能用1次，是典型的01背包问题。但是该题对背包有两个限制条件，分别是容积和重量。因此，只是在01背包的基础上增加了一个重量的循环。
动态规划五部曲：
如果当前背包容积为i，重量为j：

1. 确定递推公式
   dp[i][j]=Math.max(dp[i][j],dp[i-v][j-m]+w)
2. 确定初始化值
   dp[0][0]=0
3. 确定递推方向
   01背包既可以先物品再背包，也可以先背包再物品。
   这里的二维dp是容积与重量，需要注意的是需要遵从01背包二维dp重量倒推的原则，保证物品只被选择一次。

代码如下：

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        int N,V,M;
        Scanner scan=new Scanner(System.in);
        N=scan.nextInt();//物品数量
        V=scan.nextInt();//背包容积
        M=scan.nextInt();//背包重量
        int dp[][]=new int[V+1][M+1];
        for(int i=0;i<N;i++){
            int v=scan.nextInt();
            int m=scan.nextInt();
            int w=scan.nextInt();
            for(int j=V;j>=v;j--){
                for(int k=M;k>=m;k--){
                    dp[j][k]=Math.max(dp[j-v][k-m]+w,dp[j][k]);
                }
            }
        }
        System.out.println(dp[V][M]);
    }
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23