专做排名的网站,wordpress cascade,直播平台搭建,谷歌优化师是做什么的前言 动态规划模型从尝试暴力递归到傻缓存到动态规划 四种模型和体系班两种模型一共六种模型 0.1 从左往右模型 0.2 范围讨论模型范围尝试模型 #xff08;这种模型特别在乎讨论开头如何如何 结尾如何如何#xff09; 玩家博弈问题#xff0c;玩家玩纸牌只能那左或者右 0.3 …前言 动态规划模型从尝试暴力递归到傻缓存到动态规划 四种模型和体系班两种模型一共六种模型 0.1 从左往右模型 0.2 范围讨论模型范围尝试模型 这种模型特别在乎讨论开头如何如何 结尾如何如何 玩家博弈问题玩家玩纸牌只能那左或者右 0.3 样本对应样本对应模型特别在乎两个样本结尾如何如何 最长公共子序列 0.4 业务限制模型 动态规划只是暴力尝试的一个缓存 1.2 分析
到当前货物的时候有两种选择要么选择当前货物要么不选择当前货物 base 条件的判断分析 if (rest 0) { return -1;} 这里为什么不能取return 0因为上由传下来的剩下的bags的重量要大于0上由的值才是有意义的 递归改动态规划
第一步找确定的值
if (index w.length) {
return 0;
}
第二步找动态的值喝确定值之间的关系动态的值时如何根据静态值退出来的
int p1 process(w, v, index 1, rest);
int next process(w, v, index 1, rest - w[index]);
这辆动态函数都需要依赖他的一行最后一行又是确定值
1.3 尝试递归代码
// 所有的货重量和价值都在w和v数组里// 为了方便其中没有负数// bag背包容量不能超过这个载重// 返回不超重的情况下能够得到的最大价值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);}// index 0~N// rest 负~bagpublic 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);}
1.4 改动态规划
递归改动态规划
第一步找确定的值 第二步找动态的值喝确定值之间的关系动态的值时如何根据静态值退出来的
改动态规划 看是否有重复的情况
下面的p310都会重复 1.5 动态规划代码
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));}}
