背包系列问题之--完全背包问题

问题描述

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

问题分析

    与01背包问题不同的是，每类宝物数量无限，我们回想一下01背包问题的一维数组解法，伪代码如下：

for i = 1 to N //N为宝物种类数
  for j = M to W[i] //M为背包总容量
    f[j]=Max(f[j],f[j-W[i]]+V[i])
  end
end

    注意第二层遍历是逆序的，这是为了保证在第i次循环中的f[j]是由第i-1次循环得到的f[j-w[i]]递推而来。换句话说，这就是为了保证每件物品只被选择一次!!!
    因为宝物数量无限，所以在考虑加入一件第i类宝物时，需要一个可能已经选入第i类宝物的子结果，即每件物品可被选择多次。而顺序遍历恰好意味着第i次循环中的f[j]是由第i次循环得到的f[j-w[i]]递推而来，因此顺序循环就是完全背包问题的解！

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 treasuresClassNum=treasures.length;
            int[] f=new int[totalVolume+1];
            for(int i=0;i<treasuresClassNum;i++){
                int currentVolume=treasures[i].getVolume();
                int currentValue=treasures[i].getValue();
                for(int j=currentVolume;j<=totalVolume;j++){
                    f[j]=Math.max(f[j], f[j-currentVolume]+currentValue);
                }
            }
            maxValue=f[totalVolume];
        }
        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;
    }
}