动态规划之背包问题

 

题目

现有背包的容量是capacity

有些物品有两个属性：重量和价值。物品的重量存在于weight数组中，物品的价值存在于value数组中。为了方便起见，没有负数。

限制是每个项目只有一个，要么放在背包里，要么不放，如何使背包获得最大的价值，即背包可以在不超过背包容量的情况下从项目中获得最大的价值，最终的结果，背包不能装满。

思路一：普通递归

对于index下标的当前数组值，可以选择两种情况，比较两种情况下获得较大的价值。

public static int maxValueOne(int capacity, int[] weight, int[] value){    if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){        return 0;    }    return processOne(capacity, weight, value, 0);}/** * @param rest  背包的剩余重量 * @param weight 重量数组 * @param value 价值数组 * @param index 数组下标 * @return */public static int processOne(int rest, int[] weight, int[] value, int index){    //当剩余重量小于0时，意味着当前物品不能需要。注意:重量可能等于0和价值    //如果rest 当前index不能用于负数，因此value[index]值就无效，返回 -1    if(rest < 0){        return -1;    }    if(index == weight.length){ ///不要超过界限        return 0;    }    int next = processOne(rest - weight[index], weight, value, index +1);    int ans1 = 0;    if(next != -1){        //想要当前的物品        ans1 = value[index] + next;    }    ///不要使用当前物品    int ans2 = processOne(rest, weight, value, index + 1);    //取最大值    return Math.max(ans1, ans2);}

思路二：愚蠢的缓存方法

分析是否有重复的过程，可以根据下标配合剩余背包容量确认值。假设背包容量为20，目前index = 3.状态一是取0和2，不取1，此时剩余背包容量restt = 20 - 4 = 状态二是取1，不取2和3，此时剩余容量也为16，有重复过程。

public static int maxValueTwo(int capacity, int[] weight, int[] value){        if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){            return 0;        }        int N = weight.length;        int[][] dp = new int[N+1][capacity+1];        //初始化        for (int i = 0; i <= N; i++) {            for (int j = 0; j <= capacity; j++) {                dp[i][j] = -1;            }        }        return processTwo(capacity, weight, value, 0, dp);    }    public static int processTwo(int rest, int[] weight, int[] value, int index, int[][] dp){        if(rest < 0){            return -1;        }        if(index == weight.length){            return 0;        }        if(dp[index][rest] != -1) {            return dp[index][rest];        }        int next = processTwo(rest - weight[index], weight, value, index+1, dp);        int ans1 = 0;        if(next != -1){            ans1 = value[index] + next;        }        int ans2 = processTwo(rest, weight, value, index+1, dp);        int max = Math.max(ans1, ans2);        dp[index][rest] = max;        return max;    }

思路三:动态规划的精髓——直接取值法

public static int maxValueThree(int capacity, int[] weight, int[] value){    if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){        return 0;    }    int N = weight.length;    int[][] dp = new int[N+1][capacity+1];    ///直接赋值    for (int i = N-1; i >= 0; i--) {        for (int j = 0; j <= capacity; j++) {            ///位置值            int next = j - weight[i] < 0 ? -1 : dp[i+1][j-weight[i]];            int ans1 = 0;            if(next != -1){                ans1 = value[i] + next;            }            ///位置值不取            int ans2 = dp[i+1][j];            //比较然后存值            dp[i][j] = Math.max(ans1, ans2);        }    }    return dp[0][capacity];}

总结测试

public class Knapsacks {    public static int maxValueOne(int capacity, int[] weight, int[] value){        if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){            return 0;        }        return processOne(capacity, weight, value, 0);    }    /**     * @param rest  背包的剩余重量     * @param weight 重量数组     * @param value 价值数组     * @param index 数组下标     * @return     */    public static int processOne(int rest, int[] weight, int[] value, int index){        //当剩余重量小于0时，意味着当前物品不能需要。注意:重量可能等于0和价值        //如果rest 当前index不能用于负数，因此value[index]值就无效，返回 -1        if(rest < 0){            return -1;        }        if(index == weight.length){ ///不要超过界限            return 0;        }        int next = processOne(rest - weight[index], weight, value, index +1);        int ans1 = 0;        if(next != -1){            //想要当前的物品            ans1 = value[index] + next;        }        ///不要使用当前物品        int ans2 = processOne(rest, weight, value, index + 1);        //取最大值        return Math.max(ans1, ans2);    }    public static int maxValueTwo(int capacity, int[] weight, int[] value){        if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){            return 0;        }        int N = weight.length;        int[][] dp = new int[N+1][capacity+1];        //初始化        for (int i = 0; i <= N; i++) {            for (int j = 0; j <= capacity; j++) {                dp[i][j] = -1;            }        }        return processTwo(capacity, weight, value, 0, dp);    }    public static int processTwo(int rest, int[] weight, int[] value, int index, int[][] dp){        if(rest < 0){            return -1;        }        if(index == weight.length){            return 0;        }        if(dp[index][rest] != -1) {            return dp[index][rest];        }        int next = processTwo(rest - weight[index], weight, value, index+1, dp);        int ans1 = 0;        if(next != -1){            ans1 = value[index] + next;        }        int ans2 = processTwo(rest, weight, value, index+1, dp);        int max = Math.max(ans1, ans2);        dp[index][rest] = max;        return max;    }    public static int maxValueThree(int capacity, int[] weight, int[] value){        if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){            return 0;        }        int N = weight.length;        int[][] dp = new int[N+1][capacity+1];        ///直接赋值        for (int i = N-1; i >= 0; i--) {            for (int j = 0; j <= capacity; j++) {                ///位置值                int next = j - weight[i] < 0 ? -1 : dp[i+1][j-weight[i]];                int ans1 = 0;                if(next != -1){                    ans1 = value[i] + next;                }                ///位置值不取                int ans2 = dp[i+1][j];                //比较然后存值                dp[i][j] = Math.max(ans1, ans2);            }        }        return dp[0][capacity];    }    //生成两个数组返回    public static int[][] generateArray(int maxSize, int maxValue){        int size = (int)((maxSize + 1) * Math.random());        int[][] arr = new int[2][size];        for (int i = 0; i < size; i++) {            arr[0][i] = (int)((maxValue + 1) * Math.random());            arr[1][i] = (int)((maxValue + 1) * Math.random());        }        return arr;    }    public static void main(String[] args) {        int testTime = 1000;        int maxSize = 100;        int maxValue = 100;        for (int i = 0; i < testTime; i++) {            int[][] array = generateArray(maxSize, maxValue);            int capacity = (int)(100*(Math.random()));            int one = maxValueOne(capacity, array[0], array[1]);            int two = maxValueTwo(capacity, array[0], array[1]);            int three = maxValueThree(capacity, array[0], array[1]);            if(one != two || one != two || one != three){                System.out.println(小伙子，有点问题，再改！！！");            }        }        System.out.println(”真的很好，perfect！！！");    }}