背包问题之二维背包

package com.zhang.reflection.面试.算法模版.背包问题模版;

import java.util.Scanner;

/**
 * 问题：二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；
 * 对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，
 * 第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
 *
 * 思路：
 */

public class 二维背包 {
    //N为物品数目
    //W为背包所承载的最大重量
    //V为背包所承载的最大容量
    //weights[]为每个物品的重量
    //volume[]为每个物品的体积
    //values[]为每个物品的价值
    public static int twoDimensionKnapack(int N, int W, int V, int[] weights, int[] volume, int[] values ){
        int[][] dp = new int[W+1][V+1];

        for(int i = 0; i < N; i++){
            int w = weights[i], vi = volume[i], v = values[i];
            //逆序遍历(与01背包类似)，这里是每个物品只能使用一次，
            // 如果可以使用多次则用正序遍历，就是01背包与完全背包的区别
            for(int j = W; j >= w; j--){  
                for(int k = V; k >= vi; k--){
                    dp[j][k] = Math.max(dp[j][k], dp[j-w][k-vi]+v);
                }
            }
        }
        return dp[W][V];
    }

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        int W=sc.nextInt();
        int[] volume=new int[N];
        int[] weight=new int[N];
        int[] values=new int[N];
        for(int i=0;i<N;i++){
            volume[i]=sc.nextInt();
            weight[i]=sc.nextInt();
            values[i]=sc.nextInt();
        }
        System.out.println(twoDimensionKnapack(N,W,V,weight,volume,values));
    }
}