背包系列问题之--多重背包问题

题目描述

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

解题思路

    为了方便讨论，我们将问题描述一般化：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件物品可用，每件的耗费是w[i]，价值是v[i]，求解将哪些物品装入背包可使得耗费和不超过背包总容量且总价值最大。
(1)转换成01背包问题求解
    这是比较简单易懂的一种解题思路，把第i类物品转换为01背包中的n[i]件物品，则得到了物品数量为Σn[i]的01背包问题，直接求解其复杂度为O(V·Σn[i])，其状态转移方程:f[i][j]=max{f[i-1][j-k·w[i]]+k·v[i]} 或者f[j]=max{f[j-k·w[i]]+k·v[i]} k∈[0,n[i] ]。
    【复杂度优化】在完全背包问题中，把第i种物品拆分成耗费为w[i]·2^k， 价值为v[i]·2^k 的若干件物品，其中k满足w[i]·2^k<=V，这里利用了二进制的思想，因为不管最优策略选择几件第i种物品，总可以表示成若干件物品的和。这样就把每种物品拆分成了O(logV/w[i])件物品，时间复杂度也随之降为O(V·Σlog(V/w[i]))。同理在多重背包问题中，我们也可将第i种物品分成log(n[i])种物品，且每种只有一件，就将原问题转化成了复杂度为O(V·log(n[i]))的01背包问题。

java代码实现--时间复杂度O(v*Σn[i])

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

    //时间复杂度O(v*Σn[i])
    //状态方程f[j]=max{f[j-k*W[i]]+k*v[i]} k∈[0,n[i]]
    public static int solution1(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();
                int currentNum=treasures[i].getNum();
                for(int j=totalVolume;j>=currentVolume;j--){
                    for(int k=0;k<=currentNum&&k*currentVolume<=j;k++){
                        f[j]=Math.max(f[j], f[j-k*currentVolume]+k*currentValue);                       
                    }
                }
            }
            maxValue=f[totalVolume];
        }
        return maxValue;
    }
}

class Treasure{
    private int value;//价值
    private int volume;//体积
    private int num;//数量
    /**
     * @param value 价值
     * @param volume 体积
     * @param num 数量
     */
    public Treasure(int value,int volume,int num) {
        this.setValue(value);
        this.setVolume(volume);
        this.setNum(num);
    }
    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;
    }
    public int getNum() {
        return num;
    }
    public void setNum(int num) {
        this.num = num;
    }
}

java代码实现--时间复杂度O(v*Σlogn[i])

public class Main{
    public static void main(String[] args) {
        int totalVolume=5;//背包容量
        Treasure[] treasures={new Treasure(200, 1, 2),
                            new Treasure(100, 3, 1),
                            new Treasure(300, 2, 3),
                            new Treasure(150, 4, 2),
                            new Treasure(350, 5, 2)};
        System.out.println(soltion(treasures, totalVolume));
    }
    
    public static int soltion(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();
                int currentNum=treasures[i].getNum();
                //如果某类宝物的总体积超过了背包的最大容积，那么这退化成了一个完全背包问题
                if(currentNum*currentVolume>totalVolume){
                    completePackage(f, currentVolume, currentValue, totalVolume);
                }else {//反之就需要我们由二进制优化思想将其拆分，使其退化一个01背包问题
                    int k=1;
                    while(k<=currentNum){
                        zeroOnePackage(f, currentVolume*k, currentValue*k, totalVolume);
                        currentNum-=k;
                        k<<=1;
                    }
                    zeroOnePackage(f, currentVolume*currentNum, currentValue*currentNum, totalVolume);
                }
            }
            maxValue=f[totalVolume];
        }
        return maxValue;
    }
    
    /**
     * 01背包解法
     * @param f 一维动态规划数组
     * @param currentVolume 当前物品的体积
     * @param currentValue 当前物品的价值
     * @param totalVolume 背包的最大容积
     */
    private static void zeroOnePackage(int[] f,int currentVolume,int currentValue,int totalVolume) {
        for(int j=totalVolume;j>=currentVolume;j--){
            f[j]=Math.max(f[j], f[j-currentVolume]+currentValue);
        }
    }
    
    /**
     * 完全背包解法
     * @param f 一维动态数组
     * @param currentVolume 当前物品的体积
     * @param currentValue 当前物品的价值
     * @param totalVolume 背包的最大容积
     */
    private static void completePackage(int[] f,int currentVolume,int currentValue,int totalVolume) {
        for(int j=currentVolume;j<=totalVolume;j++){
            f[j]=Math.max(f[j], f[j-currentVolume]+currentValue);
        }
    }

}

class Treasure{
    private int value;//价值
    private int volume;//体积
    private int num;//数量
    /**
     * @param value 价值
     * @param volume 体积
     * @param num 数量
     */
    public Treasure(int value,int volume,int num) {
        this.setValue(value);
        this.setVolume(volume);
        this.setNum(num);
    }
    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;
    }
    public int getNum() {
        return num;
    }
    public void setNum(int num) {
        this.num = num;
    }
}