问题描述

    我们在上一篇文章中讨论并实现了01背包问题的解法及代码实现，接下来我们将对其时间和空间复杂度进行讨论并优化。

基本思路

    二维动态规划解法的时间复杂度已不可再优化，但是我们可以将空间复杂度由O(MN)降至O(N)，M为物品数量，N为背包容量。首先回想一下我们的二维数组解法，伪代码如下：

//二维dp数组f[i][j]
for i = 1 to M
 for j = 1 to N
   if(j<w[i])//背包总空间小于第i件宝物的体积w[i]
     f[i][j]=f[i-1][j]
   else
     f[i][j]=max(f[i-1][j]，f[i-1][j-w[i]]+v[i])
   end
 end
end

    (1)我们现在希望把空间复杂度降为O(N)，初始化一个一维动态数组f[j]，表示考虑前i件宝物时可带走的最大价值(PS:前提是第i次循环结束，否则f[j]中既有只考虑前i件时可获得的最优解的，也有只考虑前i-1件宝物时可获得的最优解)；
    (2)根据动态规划“由下而上”的思想可知，要求的第i步的最优解我们只需要根据第i-1步的最优解即可求得，并且现在是一维数组，所以我们需要对f[j]从后往前更新，这里一定要想明白！好了想明白后我们就上代码。

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 trasuresNum=treasures.length;
            int[] f=new int[totalVolume+1];
            for(int i=0;i<trasuresNum;i++){
                int currentVolume=treasures[i].getVolume();
                int currentValue=treasures[i].getValue();
                //注意这里为什么要逆序，前面已经解释过
                for(int j=totalVolume;j>=currentVolume;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;
    }
}