[数据结构+算法]关于动态规划dp入门--01背包问题
admin
2024-02-25 15:18:18
0次

(1)关于动态规划的定义:

之前买的假书害人捏......不过有个问题没说错,动态规划和递归很相似,但是动态规划利用分治法,把大问题转化为子任务,当计算出一个子任务的结果将储存起来,避免对于同一个子任务的重复计算

但其实根据某本书的写法,就是给递归套了一层存储的壳子......个人感觉这个做法不是很地道,

递归可以理解为从上而下进行的,从大任务开始,然后等待着小任务的的返回结果确认大任务的值.

而动态规划可以理解为自下而上进行的,先去计算小任务,再去计算大任务的结果

关于转移方程:怎么从小任务里面推出大任务的方式

形象一点理解就是:递归就是上面主动发布任务,动态规划就是下面把任务自己搞完了让上司验收

主动方不一样

(2)关于动态规划的举例(例题)

1.背包问题:

背包问题的描述,举例,当前有四件商品,编号为1234,所占空间为2345,价值为3456

如何有限的空间获取足够多的价值    (这种双限制的问题就该线性规划!<划掉>)

概述
编号1234
所占空间2345
价值3456

2.处理思路/转移方程:

处理思路(这里先整理动态规划的部分)如果当前的剩余空间 j ,能装下当前这个商品 i,就判断一下能否购买这个,如果装不下就手动忽略这个

状态转移方程( f(i,j) 代表当前能购买前 i 个物体,剩余空间还有 j 条件下能获取到的最大价值)

当weight[i]>j(装不下的时候)

f(i,j)=f(i-1,j)

当weight[i]<=j(能装得下)

f(i,j)=max{  f(i-1 , j)  ,  f( i-1 , j-weight[i])+value[i]  }

截止条件为

i==0(意为没有商品可以购买的时候)

3.代码思路以及实现:

//提示想算出最优解是可行的,不过要进行回溯捏
//二维数组计算的原理为:(具体画个图)自下而上开始计算
//先把0的位置都初始化,然后从(1.1)开始往前,直到把所有的情况都计算出来,
// 然后直接读取最后一个位置
//之所以称之为动态,可能是因为某次计算出的结果会作为下一次计算的基数
void f(int x, int y) {//初始化数组int arr[50][50];for (int i = 0; i < 50; i++) {for (int j = 0; j < 50; j++) {arr[i][j] = 0;}}//然后开始往里面算for (int i = 1; i <= x; i++) {for (int j = 1; j <= y; j++) {if (j >= weight[i]) {//注意这里是大于等于int m1 = arr[i - 1][j];int m2 = arr[i - 1][j - weight[i]] + value[i];arr[i][j] = m1 > m2 ? m1 : m2;}else {arr[i][j]= arr[i - 1][j];}}}//输出最终结果------------------------------------cout << arr[x][y] << endl;//遍历得到结果------------------------------------for (int i = 0; i <= x; i++) {for (int j = 0; j <= y; j++) {cout << arr[i][j] << " ";}cout << endl;}
}

同时这里补充一个回溯的方法

//根据纯动态规划的获取方法(回溯)
//回溯的原理为:判断一下当前这个东西自己能否能装下,如果能装下
//看看当前的价值是否等于之前买下的情况,如果是,则确实是买下了这个东西
//如果不是,就代表自己没买
//此外,如果装不下,也默认自己没买
void findWhat(int x,int y) {//树组是上面运行完的现成数组,我们直接进行回溯if (x >= 1) {if (y >= weight[x]) {//代表可以买到if (temp[x][y] == temp[x - 1][y - weight[x]] + value[x]) {cout << "::" << x << endl;findWhat(x - 1, y - weight[x]);}else {findWhat(x - 1, y);}}else {findWhat(x - 1, y);}}
}

关于最初长回文字串:

相关内容

热门资讯

微扑克开挂技巧!智星菠萝透视”... 微扑克开挂技巧!智星菠萝透视”切实真的有开挂课程1、实时智星菠萝透视透视辅助更新:用户可以随时随地访...
AApoker开挂技巧!wer... 您好,werplan脚本这款游戏可以开挂的,确实是有挂的,需要了解加去威信【136704302】很多...
红龙PoKer透视教程!aap... 红龙PoKer透视教程!aapoker怎么设置提高好牌几率”好像真的是有透视技法1、每一步都需要思考...
WePoKer辅助方法!fis... 您好,fishpoker透视底牌这款游戏可以开挂的,确实是有挂的,需要了解加去威信【13670430...
WPK辅助器插件!微扑克辅助下... WPK辅助器插件!微扑克辅助下载”一贯是真的有辅助器策略1、操作简单,无需微扑克辅助下载手机版透视脚...
智星菠萝德州透视挂神器!wpk... 智星菠萝德州透视挂神器!wpk透视是真的假的”果然是真的有透视挂指南1、任何wpk透视是真的假的透视...
WePoKer透视技巧!如何下... WePoKer透视技巧!如何下载德普之星辅助软件”切实真的是有透视方针如何下载德普之星辅助软件破解侠...
智星菠萝德州辅助器技巧!aap... 智星菠萝德州辅助器技巧!aapoker脚本怎么用”本来存在有辅助器经验1、该软件可以轻松地帮助玩家将...
aapoker辅助插件!wer... aapoker辅助插件!werplan透视挂”一直是有辅助积累亲,关键说明,werplan透视挂透视...
德州扑克辅助攻略!智星德州插件... 德州扑克辅助攻略!智星德州插件2024最新版”其实真的有辅助阶段1、全新机制【智星德州插件2024最...