开封景区网站建设项目方案,wordpress多文件传递变量,wordpress在线编辑慢,wordpress彩色框算法|8.从暴力递归到动态规划1 目前感觉#xff0c;背包问题和货币数组问题本质相同#xff0c;货币的与dp相关的三种代码写完了#xff0c;快复习不完了#xff0c;背包暂时先不写了#xff0c;回头再写#xff0c;补充#xff0c;再总结#xff0c;结合那个C大神的文…算法|8.从暴力递归到动态规划1 目前感觉背包问题和货币数组问题本质相同货币的与dp相关的三种代码写完了快复习不完了背包暂时先不写了回头再写补充再总结结合那个C大神的文章再弄。 背包类问题
目前来讲我接触到的背包问题有四种分别是01背包、完全背包、多重背包、以及部分背包。背包问题都属于NP问题非直接求解问题前三种一般使用动态规划进行求解后一种一般使用贪心求解。
01背包
题意给定两个长度都为N的数组weights和valuesweights[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(wnull||vnull||w.length!v.length||w.length0){return 0;}return process(w,v,0,bag);
}public static int process(int[] w, int[] v, int index, int rest) {if(rest0){return -1;}if(indexw.length){return 0;}int p1process(w,v,index1,rest);int p20;int nextprocess(w,v,index1,rest-w[index]);if(next!-1){p2v[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 Nw.length;int[][] dpnew int[N1][bag1];for (int index N-1; index 0 ; index--) {for (int rest 0; rest bag ; rest) {int p1dp[index1][rest];int p20;int nextrest-w[index]0?-1:dp[index1][rest-w[index]];if(next!-1){p2v[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背包问题很像只是这个是要求正好组成aim01背包则是不超过的方法数所以这里我们只需要在aim0时返回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 方法如下1111、112、22 一共就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(rest0){return 0;}if(indexarr.length){return rest0?1:0;}int ways0;for (int zhang 0; zhang*arr[index] rest ; zhang) {waysprocess(arr,index1,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 ways0;for (int zhang 0; zhang*arr[index] rest ; zhang) {ways(rest-zhang*arr[index]0)? 0: dp[index1][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方法1111、112、22 一共就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) {HashMapInteger, 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.EntryInteger, 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的但是张数更少的算里边了肯定错啊rest0时不需要货币即使满足也不需要了所以记得改成0
补充
这里其实可以对数组按照货币值进行预处理/排序使用迭代给sort传比较器//优先级队列面值数组不需要预处理只需要用于降序排列的比较器
核心代码
递归代码
public static int minCoins(int[] arr, int aim) {if(aim0){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是几维表确定可变参数的变化范围——是0N还是0N-1预处理边界条件确定普遍位置怎么确定边界判断——使用三目时一定要注意加括号四个角中的哪个是最终结果
例题总结
01背包——边界判断超重是-1没装够/刚好是0要和不要的两种情况pk要较小值完全背包多重背包组成aim的方法数每张认为是一种——边界判断超支/不够都是0aim0时indexarr.length都算是1;两种情况不需要pk直接相加返回组成aim的方法数每种张数无限——边界判断超支/不够都是0aim0时indexarr.length都算是1;不是两种情况了对有效的张数一个条件进行遍历总方法相加组成aim的方法数每种张数有限——边界判断超支/不够都是0aim0时indexarr.length都算是1;不是两种情况了对有效的张数两个条件进行遍历总方法相加组成aim的最小货币数每张张数无限——边界条件判断初值都为最大值除了aim0时递归那aim0一定在非法条件的前边next值有效的判断两种情况pk要最小的
三种dp解法背包问题区别
略
前三种dp解法货币数组区别
注这里返回的都是方法数肯定是越多越好不涉及边界值返回的系列问题。
货币数组类型决定了是否需要张数遍历面值 不用张数有限无限决定了张数遍历的条件是1个还是两个一般都是index倒序rest正序
注区分面值数组、货币数组
前者是天然去重后者可能存在相同的看题目设定决定是否需要进行预处理
另本类型开头的那种其实也算是面值数组了。
两种情况了对有效的张数一个条件进行遍历总方法相加
组成aim的方法数每种张数有限——边界判断超支/不够都是0aim0时indexarr.length都算是1;不是两种情况了对有效的张数两个条件进行遍历总方法相加组成aim的最小货币数每张张数无限——边界条件判断初值都为最大值除了aim0时递归那aim0一定在非法条件的前边next值有效的判断两种情况pk要最小的
三种dp解法背包问题区别
略
前三种dp解法货币数组区别
注这里返回的都是方法数肯定是越多越好不涉及边界值返回的系列问题。
货币数组类型决定了是否需要张数遍历面值 不用张数有限无限决定了张数遍历的条件是1个还是两个一般都是index倒序rest正序
注区分面值数组、货币数组
前者是天然去重后者可能存在相同的看题目设定决定是否需要进行预处理
另本类型开头的那种其实也算是面值数组了。
