算法8.从暴力递归到动态规划1

算法|8.从暴力递归到动态规划1

目前感觉，背包问题和货币数组问题本质相同，货币的与dp相关的三种代码写完了，快复习不完了，背包暂时先不写了，回头再写，补充，再总结，结合那个C++大神的文章再弄。

背包类问题

目前来讲，我接触到的背包问题有四种分别是01背包、完全背包、多重背包、以及部分背包。背包问题都属于NP问题（非直接求解问题），前三种一般使用动态规划进行求解，后一种一般使用贪心求解。

01背包

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

解题思路：

• 先写出递归版本，然后对照着改dp。
• 要与不要。结果越大越好，是正向决策，同时使用的累加。
• 参数设置：重量数组w、价值数组v、当前决策到的坐标index、背包剩余的空间rest
• 可变参数为index和rest，所以dp表是一张二维表。

核心代码：

递归代码：

public static int maxValue(int[] w, int[] v, int bag) {
    if(w==null||v==null||w.length!=v.length||w.length==0){
        return 0;
    }
    return process(w,v,0,bag);
}

public static int process(int[] w, int[] v, int index, int rest) {
    if(rest<0){
        return -1;
    }
    if(index==w.length){
        return 0;
    }
    int p1=process(w,v,index+1,rest);
    int p2=0;
    int next=process(w,v,index+1,rest-w[index]);
    if(next!=-1){
        p2=v[index]+next;
    }
    return Math.max(p1,p2);
}

dp代码：

public static int dp(int[] w, int[] v, int bag) {
    if (w == null || v == null || w.length != v.length || w.length == 0) {
        return 0;
    }
    int N=w.length;
    int[][] dp=new int[N+1][bag+1];
    for (int index = N-1; index >=0 ; index--) {
        for (int rest = 0; rest <=bag ; rest++) {
            int p1=dp[index+1][rest];
            int p2=0;
            int next=rest-w[index]<0?-1:dp[index+1][rest-w[index]];
            if(next!=-1){
                p2=v[index]+next;
            }
            dp[index][rest]=Math.max(p1,p2);
        }
    }
    return dp[0][bag];
}

测试代码：

public static void main(String[] args) {
    int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
    int[] values = { 5, 6, 3, 19, 12, 4, 2 };
    int bag = 15;
    System.out.println(maxValue(weights, values, bag));
    System.out.println(dp(weights, values, bag));
}

测试结果：

完全背包

题意：有 N种物品和一个容量为C的背包，每种物品都有无限件。第 i件物品的体积是 v[i]，价值是w[i] .求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

解题思路：

核心代码：

测试代码：

测试结果：

多重背包

题意：有 N种物品和一个容量为C的背包，数量为s[i]。第 i件物品的体积是 v[i]，价值是w[i] .求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解题思路：

核心代码：

测试代码：

测试结果：

货币类问题

组成aim的方法数（每张认为是一种）

题意：arr是货币数组，其中的值都是正数。再给定一个正数aim。
每个值都认为是一张货币，即便是值相同的货币也认为每一张都是不同的，
返回组成aim的方法数。例如：arr = {1,1,1}，aim = 2。
第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2
一共就3种方法，所以返回3

解题思路：

• 这一题其实和01背包问题很像，只是这个是要求正好组成aim，01背包则是不超过的方法数
• 所以这里我们只需要在aim=0时返回1，总金额超过了|根本就组不成（钱不够）就返回0
• 注意：改写过程中三目操作符建议加上括号（血淋淋的教训…）// dp[index][rest] = dp[index + 1][rest] + (rest - arr[index]) < 0 ? 0 : dp[index + 1][rest - arr[index]];

核心代码：

暴力递归：

public static int coinWays(int[] arr, int aim) {
    return process(arr, 0, aim);
}

public static int process(int[] arr, int index, int rest) {
    if (rest < 0) {
        return 0;
    }
    if (index == arr.length) {
        return rest == 0 ? 1 : 0;
    }
    return process(arr, index + 1, rest - arr[index])
            + process(arr, index + 1, rest);
}

dp:

    public static int dp(int[] arr, int aim) {
        if (aim == 0) {
            return 1;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
//                dp[index][rest] = dp[index + 1][rest] + (rest - arr[index]) < 0 ? 0 : dp[index + 1][rest - arr[index]];
                dp[index][rest] = dp[index + 1][rest] + (rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : 0);
            }
        }
        return dp[0][aim];
    }

测试代码：

略

测试结果：

组成aim的方法数（每种张数无限）

题意：arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
每个值都认为是一种面值，且认为张数是无限的。返回组成aim的方法数
例如：arr = {1,2}，aim = 4 方法如下：1+1+1+1、1+1+2、2+2
一共就3种方法，所以返回3。

解题思路：

• 大体思路和上边相同，只不过子过程需要对要用多少张数进行遍历
• 张数遍历时循环条件为zhang * arr[index] <= rest，对应的dp改写中也需要遍历（如果不优化的，优化之后再说，这里应该是可以进行斜率优化）

核心代码：

递归：

public static int coinsWay(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    return process(arr, 0, aim);
}

public static int process(int[] arr, int index, int rest) {
    if(rest<0){
        return 0;
    }
    if(index==arr.length){
        return rest==0?1:0;
    }
    int ways=0;
    for (int zhang = 0; zhang*arr[index] < rest ; zhang++) {
        ways+=process(arr,index+1,rest-zhang*arr[index]);
    }
    return ways;
}

dp:

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            int ways=0;
            for (int zhang = 0; zhang*arr[index] < rest ; zhang++) {
                ways+=(rest-zhang*arr[index]<0)? 0: dp[index+1][rest-zhang*arr[index]];
            }
            dp[index][rest]=ways;
        }
    }
    return dp[0][aim];
}

测试代码：

略

测试结果：

组成aim的方法数（每种张数有限）

题意：arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，认为值相同的货币没有任何不同，返回组成aim的方法数

例如：arr = {1,2,1,1,2,1,2}，aim = 4方法：1+1+1+1、1+1+2、2+2
一共就3种方法，所以返回3

解题思路：

• 本题思路与上题类似，只是张数变成有限的了，对应的遍历张数的条件多了一个
• 另外，本题不是给两个数组一个张数组和值数组，所以我们还需要对数据进行预处理，封装，并进行数据统计，并提供对应方法让外部调用。
• 封装构造方法初始化大小确定（我们给的）；getInfo是我们进行的词频统计，根据arr,涉及到containKey,put等方法

核心代码：

递归代码：

public static class Info {
    private int[] coins;
    private int[] zhangs;

    public Info(int[] coins, int[] zhangs) {
        this.coins = coins;
        this.zhangs = zhangs;
    }
}

public static Info getInfo(int[] arr) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num : arr) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }
    int N = map.size();
    int[] coins = new int[N];
    int[] zhangs = new int[N];
    int index = 0;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        coins[index] = entry.getKey();
        zhangs[index] = entry.getValue();
    }
    Info info = new Info(coins, zhangs);
    return info;
}


public static int coinsWay(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    Info info = getInfo(arr);
    return process(info.coins, info.zhangs, 0, aim);
}

public static int process(int[] coins, int[] zhangs, int index, int rest) {
    if (rest < 0) {
        return 0;
    }
    if (index == coins.length) {
        return rest == 0 ? 1 : 0;
    }
    int ways = 0;
    for (int zhang = 0; zhang < zhangs.length && (zhang * coins[index] < rest); zhang++) {
        ways += process(coins, zhangs, index + 1, rest - zhang * coins[index]);
    }
    return ways;
}

dp代码：

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    Info info = getInfo(arr);
    int[] coins = info.coins;
    int[] zhangs = info.zhangs;
    int N = coins.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            int ways = 0;
            for (int zhang = 0; zhang < zhangs.length && (zhang * coins[index] < rest); zhang++) {
                ways += (rest - zhang * coins[index] < 0) ? 0 : dp[index + 1][rest - zhang * coins[index]];
            }
            dp[index][rest] = ways;
        }
    }
    return dp[0][aim];
}

测试代码：略

测试结果：

组成aim的最小货币数（每张张数无限）

题意：arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数。

解题思路：

• 还是需要对张数进行遍历，只不过只有一个条件
• 接受结果值设为整数最大值，最终结果返回较小值
• 另外另外，边界条件不满足条件的值需要修改成最大值，不难咱们得犯大难了，遭老罪了！要不然你计算的时候把没有组成aim的，但是张数更少的算里边了，肯定错啊；rest==0时，不需要货币，即使满足也不需要了，所以记得改成0

补充：

• 这里其实可以对数组按照货币值进行预处理/排序（使用迭代给sort传比较器//优先级队列）
• 面值数组，不需要预处理，只需要用于降序排列的比较器

核心代码：

递归代码：

public static int minCoins(int[] arr, int aim) {
    if(aim==0){
        return 0;
    }
    if (arr == null || arr.length == 0 || aim < 0) {
        return Integer.MAX_VALUE;
    }
    return process(arr, 0, aim);
}

public static int process(int[] arr, int index, int rest) {
    if (rest < 0) {
        return Integer.MAX_VALUE;
    }
    if (index == arr.length) {
        return rest == 0 ? 0 : Integer.MAX_VALUE;
    }
    int ans = Integer.MAX_VALUE;
    for (int zhang = 0; zhang * arr[index] < rest; zhang++) {
        int next = process(arr, index + 1, rest - zhang * arr[index]);
        if (next != Integer.MAX_VALUE && next > 0) {//要不然最大值加最大值可能滚成负数
            ans = Math.min(next, ans);
        }
    }
    return ans;
}

dp代码：

public static int dp(int[] arr, int aim) {
    if (aim == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 0;
    for (int j = 1; j <= aim; j++) {
        dp[N][j] = Integer.MAX_VALUE;
    }
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            int ans = Integer.MAX_VALUE;
            for (int zhang = 0; zhang * arr[index] < rest; zhang++) {
                int next = (rest - zhang * arr[index] < 0) ? Integer.MAX_VALUE : dp[index + 1][rest - zhang * arr[index]];
                if (next != Integer.MAX_VALUE && next > 0) {//要不然最大值加最大值可能滚成负数
                    ans = Math.min(next, ans);
                }
            }
            dp[index][rest]=ans;
        }
    }
    return dp[0][aim];
}

测试代码：略

测试结果：

从左到右尝试模型总结1

改写规则：

• 确定可变参数个数——dp是几维表
• 确定可变参数的变化范围——是0_N还是0N-1
• 预处理（边界条件）
• 确定普遍位置怎么确定
• 边界判断——使用三目时一定要注意加括号😥
• 四个角中的哪个是最终结果

例题总结：

• 01背包——边界判断：超重是-1，没装够/刚好是0；要和不要的两种情况pk，要较小值
• 完全背包
• 多重背包
• 组成aim的方法数（每张认为是一种）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;两种情况不需要pk，直接相加返回
• 组成aim的方法数（每种张数无限）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;不是两种情况了，对有效的张数（一个条件）进行遍历，总方法相加
• 组成aim的方法数（每种张数有限）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;不是两种情况了，对有效的张数（两个条件）进行遍历，总方法相加
• 组成aim的最小货币数（每张张数无限）——边界条件判断：初值都为最大值，除了aim=0时，递归那aim=0一定在非法条件的前边，next值有效的判断；两种情况pk，要最小的

三种dp解法背包问题区别：

略

前三种dp解法货币数组区别：

注：这里返回的都是方法数，肯定是越多越好，不涉及边界值返回的系列问题。

1. 货币数组类型决定了是否需要张数遍历（面值 不用）
2. 张数有限无限决定了张数遍历的条件是1个还是两个
3. 一般都是index倒序，rest正序

注：区分面值数组、货币数组

前者是天然去重，后者可能存在相同的，看题目设定决定是否需要进行预处理

另本类型开头的那种，其实也算是面值数组了。文章来源地址https://www.toymoban.com/news/detail-472179.html

两种情况了，对有效的张数（一个条件）进行遍历，总方法相加

• 组成aim的方法数（每种张数有限）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;不是两种情况了，对有效的张数（两个条件）进行遍历，总方法相加
• 组成aim的最小货币数（每张张数无限）——边界条件判断：初值都为最大值，除了aim=0时，递归那aim=0一定在非法条件的前边，next值有效的判断；两种情况pk，要最小的

三种dp解法背包问题区别：

略

前三种dp解法货币数组区别：

注：这里返回的都是方法数，肯定是越多越好，不涉及边界值返回的系列问题。

1. 货币数组类型决定了是否需要张数遍历（面值 不用）
2. 张数有限无限决定了张数遍历的条件是1个还是两个
3. 一般都是index倒序，rest正序

注：区分面值数组、货币数组

前者是天然去重，后者可能存在相同的，看题目设定决定是否需要进行预处理

另本类型开头的那种，其实也算是面值数组了。

到了这里，关于算法8.从暴力递归到动态规划1的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！