动态规划——背包问题

题目

给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?

该题暴力解法和详细分析过程请参考这篇博客——暴力递归——从左往右的尝试模型2，背包问题。

很明显，这个题暴力解的时候也会有大量重复计算，请看下图：

我们跳过记忆化搜索的阶段，直接来改成经典的动态规划，可以先参考这篇文章——从暴力递归到动态规划，记忆化搜索。这篇文章详细分析了加缓存的动态规划（记忆化搜索）和经典动态规划的改法。

暴力递归的过程就是动态转义方程，并且改动态规划只需依照暴力递归的过程来改，跟题意已经解耦了。

所以这里直接贴上这个题经典的暴力解法：

public static int process2(int[] w,int[] v,int index,int rest) {
        if(rest<0) {
            return -1;
        }
        if(index==w.length) {
            return 0;
        }
        int p1=process2(w, v, index+1, rest);
        int p2next=process2(w, v, index+1, rest-w[index]);
        int p2=-1;
        if(p2next!=-1) {
            p2=p2next+v[index];
        }
        return Math.max(p1, p2);
    }
    
    public static int maxValue2(int[] w,int[] v,int bag) {
        if(w==null || v==null || w.length!=v.length || w.length==0) {
            return 0;
        }
        return process2(w, v, 0, bag);
    }

很明显，可变参数只有index和rest，所以是一张二维表。

1）rest<0，所以rest左侧区域无效；

if(rest<0) {
    return -1;
}

2）index==w.length，所以第5行全是0；

if(index==w.length) {
    return 0;
}

3）除此以外，上一行总是依赖下一行；并且在每一行都是从左往右开始填；

for(int index=N-1; index>=0; index--) {
            for(int rest=0; rest<=bag; rest++) {
                int p1=dp[index+1][rest];
                int p2=-1;
                if(rest-w[index]>0) {
                    p2=v[index]+dp[index+1][rest-w[index]];
                }
                dp[index][rest]=Math.max(p1, p2);
            }
        }

4）返回 dp0，就是结果。

return process2(w, v, 0, bag);

完整代码：

package com.harrison.class13;

public class Code03_Knapsack {
    public static int process2(int[] w,int[] v,int index,int rest) {
        if(rest<0) {
            return -1;
        }
        if(index==w.length) {
            return 0;
        }
        int p1=process2(w, v, index+1, rest);
        int p2next=process2(w, v, index+1, rest-w[index]);
        int p2=-1;
        if(p2next!=-1) {
            p2=p2next+v[index];
        }
        return Math.max(p1, p2);
    }
    
    public static int maxValue2(int[] w,int[] v,int bag) {
        if(w==null || v==null || w.length!=v.length || w.length==0) {
            return 0;
        }
        return process2(w, v, 0, bag);
    }
    
    public static int dpway(int[] w,int[] v,int bag) {
        int N=w.length;
        int[][] dp=new int[N+1][bag+1];
        // 因为Java中，数组初始化默认全是0，所以base case2可以不用特意初始化为0
        for(int index=N-1; index>=0; index--) {
            for(int rest=0; rest<=bag; rest++) {
                int p1=dp[index+1][rest];
                int p2=-1;
                if(rest-w[index]>=0) {
                    p2=v[index]+dp[index+1][rest-w[index]];
                }
                dp[index][rest]=Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }
    
    public static void main(String[] args) {
        int[] w = { 3, 2, 4, 7, 3, 1, 7 };
        int[] v = { 5, 6, 3, 19, 12, 4, 2 };
        int bag=15;
        System.out.println(maxValue2(w, v, bag));
        System.out.println(dpway(w, v, bag));
    }
}