題目描述

????小偷深夜?jié)撊胍患抑閷毜暄枋辏昀镉?類寶物，重量分別為W{1,3,2,4,5}诱篷，各類寶物的體積為C{2,1,3,1,2}壶唤，對(duì)應(yīng)的價(jià)值為V{200,100,300,150,350 }。小偷隨身只攜帶了一個(gè)容量為5棕所，承重為4的背包视粮，問(wèn)小偷應(yīng)如何選擇才能使偷得寶物的價(jià)值最大？

思路分析

????在這個(gè)問(wèn)題中橙凳，對(duì)于每件物品蕾殴，具有體積和重量?jī)煞N不同的耗費(fèi)，選擇這件物品就必須同時(shí)付出兩種代價(jià)岛啸。所以我們的狀態(tài)方程如下：
????????????????????????f[i][j][k]=max{f[i-1][j][k],f[i-1][j-w[i]][k-c[i]]+v[i]}
同樣我們也可降維成二維數(shù)組被因！

Java代碼實(shí)現(xiàn)

/**
 * 二維耗費(fèi)的背包問(wèn)題
 * @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;//價(jià)值
    private int weight;//重量
    private int volume;//體積
    /**
     * @param value //價(jià)值
     * @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;
    }
}