蓝桥杯日常挑战 - 背包问题(二)：二维成本的背包优化问题

类似01背包，只是多了一个维度，那么这里再用之前介绍的动态规划思路来思考一下。
第一步：缩小规模。考虑n个物品，那我就先考虑1个物品，再考虑2个物品…，需要一个维度表示当前考虑的物品个数。
第二步：限制。
（1）所选物品个数不能超过背包容量，那么需要一个维度记录当前背包的容量。
（2）所选物品个数不能超过背包重量，那么需要一个维度记录当前背包的重量。
第三步：写出dp数组。dp[i][j][k]表示当前考虑了前i个物品，背包容量为j，重量为k时的最大价值。
第四步：推状态转移方程。dp[i][j][k]应该从哪里转移过来呢，必然是从前i-1个物品转移，我要考虑两种情况，对于第i个物品，可以选择要它，也可以不要它，如果要第i个物品，我就需要背包里面给我预留出第i个物品的体积和重量，也就是从a[i-1][j-v[i]][k-m[i]]转移，同时也能获得该物品的价值。如果不要第i个物品，那么之前从前一个状态相同容量的背包转移过来就行，即a[i-1][j][k]。
综上状态转移方程如下
$a[i][j]=max(a[i-1][j][k],a[i-1][j-v[i]][k-m[i]]+w[i])$
考虑写代码了
第一步：确定好遍历顺序，对于背包问题，一般第一个for遍历规模，第二个for遍历限制，但是我们有两个限制所以需要两个嵌套的for循环分别表示容量和重量。
代码如下，

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();//容积
		int mm = scanner.nextInt();//重量
		int[] v = new int[n+1];//容积
		int[] w = new int[n+1];
		int[] m = new int[n+1];//重量
		for (int i = 1; i < n+1; i++) {
			v[i] = scanner.nextInt();//容积
			m[i] = scanner.nextInt();//重量
			w[i] = scanner.nextInt();
		}
		int[][][] dp = new int[n+1][k + 1][mm + 1];
		for (int j = 1; j <= n; j++) {
			for (int i = 1; i <= k; i++) {
				for (int q = 1; q <= mm; q++)
					{
					dp[j][i][q] = dp[j-1][i][q];
					if(i>=v[j]&&q>=m[j])
					    dp[j][i][q] = Math.max(dp[j][i][q], dp[j-1][i - v[j]][q - m[j]] + w[j]);
					}
			}
		}
        //for (int i = 1; i < dp.length; i++) {
			
		//}
		System.out.println(dp[n][k][mm]);
	}
}