背包系列问题之--01背包(要求背包必须装满)

问题描述

    小偷深夜潜入一家珠宝店，店里有5件宝物，重量分别为W{1,3,2,4,5}，对应的价值为V{200,100,300,150,350 }。小偷随身只携带了一个承重为5的背包，问小偷应如何选择才能使偷得宝物的价值最大并要求背包必须恰好装至承重极限值？

问题分析

    题目条件要求背包必须恰好装至承重极限值(后文简称"装满条件")，解题关键就在这里。还是从我们的动态规划数组的逐步求解过程着手分析，定义数组f[j]。
    (1)当我们不考虑“装满条件时”，直接将数组初始状态全部置为0，表示在仅有前0件物品可供选择时，对于背包承重从0至W(max)都有一个合法解，那就是装入0件物品到背包；
    (2)如果考虑了“装满条件”呢，我们还可以把数组初始状态全部置为0吗？显然不能，因为除了背包承重为0这种情况其他的都不满足“装满条件”，0件物品恰好装满承重为0的包，却不能装满承重为j (j!=0)的包。所以f[j]的初始化状态: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步的最优解都是根据第i-1步推得，要想第i步获得的结果恰好装满，那么第i-1步也必须是恰好装满的最优解，否则第i-1的解也应该为Integer.minValue，因为Integer.minValue+W[i]=Integer.minValue。
综上：背包必须恰好装至承重极限值即是要求f[j]的值为非Integer.minValue的合理范围的实数(这个问题中是合理范围的正整数)!!!

Java代码实现

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));    
    }

    //借用一维数组解决问题 f[w]=max{f[w],f[w-w[i]]+v[i]} 要求装满
    public static int solution(Treasure[] treasures,int totalVolume) {
        int maxValue=-1;
        //参数合法性检查
        if(treasures==null||treasures.length==0||totalVolume<0){
            maxValue=0;
        }else {
            int tresureNum=treasures.length;
            int[] f=new int[totalVolume+1];
            //动态规划数组初始化，重要！！！
            for(int i=0;i<f.length;i++){
                if(i==0) f[i]=0;
                else f[i]=Integer.MIN_VALUE;
            }
            //动态求解
            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;//价值
    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;
    }
}