一、01背包问题 图解+详细解析 (转载)
https://blog.csdn.net/qq_37767455/article/details/99086678
:Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积,定义V(i,j):当前背包容量 j,前 i 个物品最佳组合对应的价值
大概看懂,并根据公式手填了一下表格
最优性原理的基本思想是:一个问题的最优解包含了其子问题的最优解。换句话说,一个问题的最优解可以通过其子问题的最优解递推得到。
最优性原理的应用条件是问题具有最优子结构,即一个问题的最优解可以通过其子问题的最优解递推得到。如果一个问题不具有最优子结构,则不能使用动态规划算法求解。
疑问:原理?为什么是这样的公式呢?
二、【动态规划】01背包问题(通俗易懂,超基础讲解)
https://blog.csdn.net/qq_38410730/article/details/81667885
【好的理解评论?】
我认为那个对于面对一个商品的可能性的描述应该是这样:
1.包的总容量比商品体积小,即使不装其他商品也不可能装得下该商品,此时价值与前i-1个商品的价值一样,即v[i][j]=v[i-1][j];
2.包的总容量大于等于该商品,但若拿出其它商品来获得容量装该商品,此时价值不一定大于前i-1个商品的最大价值,所以在装与不装该商品之间选定一个,即V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}
【评论】
j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}
各位老师,我对这个迭代公式的理解:V(i,j)是指让你最多装j容量的情况下,前i个商品的最大价值,其实是根据题目最终的容量来定义的,也就是让你最多装8容量,求前4个商品的最大价值。那么可以这么理解,第i个商品装不下,那只能装前i-1个商品,V(i,j)就等于V(i-1,j);第i个商品装的下,装和不装两种情况的最优价值是不一样的,取一个最大值,V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)},V(i-1,j-w(i))+v(i)这个表示我装第i个商品,那么前i-1个商品只能让你最多装j-w(i)的情况下的最大价值。
【】
在状态表V(i,j)中 “j” 就是表示当前背包的总容量。并且在状态转移方程中 V(i-1,j-w(i)) 也并不是说当前背包容量减少了w(i),而是说为了在当前容量为 j 的背包中装入容量为w(i)的物品,所以往前寻找背包容量为 j-w(i) 的状态下的最优值 V(i-1,j-w(i)),这也是状态转移方程的意义所在。
【】
V(0,j):当前背包容量为j,前0个物品最佳组合对应的价值,肯定是0啊(没放东西);
V(i,0):当前背包容量为0,前j个物品最佳组合对应的价值,肯定是0啊(放不进去)。
【???】
动态规划推导不出来递推关系式怎么搞?-- 多看看一些动态规划的例子,感觉一下,这只能多做些题目,就有思路了。
【】
我在手动填表格的时候才真正理解V(i-1,j-w(i))的意思。例如V(4,8),背包容量为8的时候,是否塞入第4个商品的最优V。塞入第4个商品的解为:因为第4个商品的W是5,先在背包腾出5的空间(既定要放进第4个商品),也就是空间为3的最优解加上第4个商品的价值v4。
三、动态规划 原理
1、动态规划中的无后效性(Principle of Optimality)指的是,一个问题的最优解包含了其子问题的最优解,且子问题的最优解不受后续决策的影响。换句话说,一个问题的最优解可以通过其子问题的最优解递推得到,而且子问题的最优解不受后续决策的影响。
这个性质是动态规划算法的核心原理之一,也是其能够高效求解具有最优子结构问题的关键。在动态规划算法中,问题被分解成一系列子问题,并通过递推的方式求解子问题的最优解。在求解过程中,使用了一些启发式规则和策略来指导搜索过程,从而加速搜索并提高搜索结果的质量。同时,通过保存已经求解的子问题的结果,避免了重复计算,提高了算法的效率。
需要注意的是,无后效性是动态规划算法的基本性质之一,但并不是所有问题都具有无后效性。如果一个问题不具有无后效性,则不能使用动态规划算法求解。因此,在使用动态规划算法时,需要先确定问题是否具有无后效性,以避免错误的求解方法。
2、什么是无后效性?
https://blog.csdn.net/qq_30137611/article/details/77655707
所谓无后效性原则,指的是这样一种性质:某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说,“未来与过去无关”,当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过程未来的演变。具体地说,如果一个问题被划分各个阶段之后,阶段k中的状态只能通过阶段k+1中的状态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没有关系,这就是无后效性
https://baike.baidu.com/item/%E6%97%A0%E5%90%8E%E6%95%88%E6%80%A7/1135283
3、什么是动态规划(Dynamic Programming)?动态规划的意义是什么?
https://www.zhihu.com/question/23995189
四、 完全背包
https://zhuanlan.zhihu.com/p/93857890
完全背包(unbounded knapsack problem)与01背包不同就是每种物品可以有无限多个:一共有N种物品,每种物品有无限多个,第i(i从1开始)种物品的重量为w[i],价值为v[i]。在总重量不超过背包承载上限W的情况下,能够装入背包的最大价值是多少?