【学习草稿】背包问题

一、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的情况下，能够装入背包的最大价值是多少？