問題描述

????小偷深夜?jié)撊胍患抑閷毜辏昀镉?件寶物，重量分別為W{1,3,2,4,5}，對應(yīng)的價(jià)值為V{200,100,300,150,350 }仲义。小偷隨身只攜帶了一個承重為5的背包，問小偷應(yīng)如何選擇才能使偷得寶物的價(jià)值最大并要求背包必須恰好裝至承重極限值？

問題分析

????題目條件要求背包必須恰好裝至承重極限值(后文簡稱"裝滿條件")埃撵，解題關(guān)鍵就在這里赵颅。還是從我們的動態(tài)規(guī)劃數(shù)組的逐步求解過程著手分析，定義數(shù)組f[j]暂刘。
????(1)當(dāng)我們不考慮“裝滿條件時(shí)”饺谬，直接將數(shù)組初始狀態(tài)全部置為0，表示在僅有前0件物品可供選擇時(shí)谣拣，對于背包承重從0至W(max)都有一個合法解募寨，那就是裝入0件物品到背包；
????(2)如果考慮了“裝滿條件”呢森缠，我們還可以把數(shù)組初始狀態(tài)全部置為0嗎拔鹰？顯然不能，因?yàn)槌吮嘲兄貫?這種情況其他的都不滿足“裝滿條件”贵涵，0件物品恰好裝滿承重為0的包列肢，卻不能裝滿承重為j (j!=0)的包。所以f[j]的初始化狀態(tài):f[0]=0宾茂，f[j]=Integer.minValue (j!=0);
????(3)為什么要選擇置為Integer.minValue呢瓷马？由f[j]=Math.max(f[j],f[j-w[i]]+v[i])知，第i步的最優(yōu)解都是根據(jù)第i-1步推得跨晴，要想第i步獲得的結(jié)果恰好裝滿欧聘，那么第i-1步也必須是恰好裝滿的最優(yōu)解，否則第i-1的解也應(yīng)該為Integer.minValue端盆，因?yàn)镮nteger.minValue+W[i]=Integer.minValue怀骤。
綜上：背包必須恰好裝至承重極限值即是要求f[j]的值為非Integer.minValue的合理范圍的實(shí)數(shù)(這個問題中是合理范圍的正整數(shù))!!!

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

public class Main{
    public static void main(String[] args) {    
        int totalWeight=5;//背包容量
        Treasure[] packages={new Treasure(200, 1),
                            new Treasure(100, 3),
                            new Treasure(300, 2),
                            new Treasure(150, 4),
                            new Treasure(350, 5)};
        System.out.println(solution(packages, totalWeight));    
    }

    //借用一維數(shù)組解決問題 f[w]=max{f[w],f[w-w[i]]+v[i]} 要求裝滿
    public static int solution(Treasure[] treasures,int totalVolume) {
        int maxValue=-1;
        //參數(shù)合法性檢查
        if(treasures==null||treasures.length==0||totalVolume<0){
            maxValue=0;
        }else {
            int tresureNum=treasures.length;
            int[] f=new int[totalVolume+1];
            //動態(tài)規(guī)劃數(shù)組初始化，重要；烂睢＝住！
            for(int i=0;i<f.length;i++){
                if(i==0) f[i]=0;
                else f[i]=Integer.MIN_VALUE;
            }
            //動態(tài)求解
            for(int i=0;i<tresureNum;i++){
                int currentVolume=treasures[i].getVolume();
                int curentValue=treasures[i].getValue();
                for(int j=totalVolume;j>=currentVolume;j--){
                    f[j]=Math.max(f[j], f[j-currentVolume]+curentValue);
                }
            }
            maxValue=f[totalVolume];
            if(maxValue<0) maxValue=-1;
        }
        return maxValue;
    }
}

class Treasure{
    private int value;//價(jià)值
    private int volume;//重量
    public Treasure(int value,int volume) {
        this.setValue(value);
        this.setVolume(volume);
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public int getVolume() {
        return volume;
    }
    public void setVolume(int volume) {
        this.volume = volume;
    }
}