动态规划——背包问题

题目

给定两个长度都为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));
    }
}
上一篇:动态规划——多样本位置全对应的尝试模型,两个字符串的最长公共子序列问题


下一篇:动态规划——StickersToSpellWord