背包问题系列之--二维费用的背包问题

题目描述

    小偷深夜潜入一家珠宝店，店里有5类宝物，重量分别为W{1,3,2,4,5}，各类宝物的体积为C{2,1,3,1,2}，对应的价值为V{200,100,300,150,350 }。小偷随身只携带了一个容量为5，承重为4的背包，问小偷应如何选择才能使偷得宝物的价值最大？

思路分析

    在这个问题中，对于每件物品，具有体积和重量两种不同的耗费，选择这件物品就必须同时付出两种代价。所以我们的状态方程如下：
                        f[i][j][k]=max{f[i-1][j][k],f[i-1][j-w[i]][k-c[i]]+v[i]}
同样我们也可降维成二维数组！

Java代码实现

/**
 * 二维耗费的背包问题
 * @author Administrator
 * @version 2018/10/12
 */
public class Exe35_PackageTwoCostDimensions {

    public static void main(String[] args) {
        
        int maxVolume=5;
        int maxWeight=4;
        NewPackage[] packages={new NewPackage(200, 1, 2),
                                new NewPackage(100, 3, 1),
                                new NewPackage(300, 2, 3),
                                new NewPackage(150, 4, 1),
                                new NewPackage(350, 5, 2)};
        System.out.println(solution(packages, maxVolume, maxWeight));

    }
    
    public static int solution(NewPackage[] packages,int maxVolume,int maxWeight) {
        int maxValue=-1;
        if(packages==null||packages.length==0||maxWeight<0||maxVolume<0){
            maxValue=0;
        }else {
            
            int packageNum=packages.length;
            int[][] f=new int[maxWeight+1][maxVolume+1];
            for(int i=0;i<packageNum;i++){
                int currentValue=packages[i].getValue();
                int currentWeight=packages[i].getWeight();
                int currentVolume=packages[i].getVolume();
                for(int j=maxWeight;j>=currentWeight;j--){
                    for(int k=maxVolume;k>=currentVolume;k--){
                        f[j][k]=Math.max(f[j][k], f[j-currentWeight][k-currentVolume]+currentValue);
                    }
                }
            }
            maxValue=f[maxWeight][maxVolume];
            
        }
        return maxValue;
    }

}

class NewPackage{
    private int value;//价值
    private int weight;//重量
    private int volume;//体积
    /**
     * @param value //价值
     * @param weight //重量
     * @param volume //体积
     */
    public NewPackage(int value,int weight,int volume) {
        this.setValue(value);
        this.setWeight(weight);
        this.setVolume(volume);
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
    public int getVolume() {
        return volume;
    }
    public void setVolume(int volume) {
        this.volume = volume;
    }
    @Override
    public String toString() {
        return "treasure"+value+weight+volume;
    }
}