恕在下愚钝，01背包问题学了两仨天才搞懂，其中也是断断续续了，
这个问题也是讲烂了的一个知识点，但是由于没有找到一个适合以自己的思维来理解的，所以现在总结一下
大家都说这是一个关于动态规划的问题，但在下才疏学浅，始终无法，理会这其中的关系，
唯一能联想到的就是高中的时候，学过的几何绘画动态规划了，特征是：给出限制条件，求最值。看来应该是这类题目了。
现在只考虑01背包的情况，至于动态规划的思想还要再接触几个相应的题目才能掌握。
首先，在网上找了大量文章，有些人上来就是给个状态方程，或者表格之类的，研究了好多，还是一知半解。好吧，路子野的人没有听说过什么叫状态方程。
后来才发现，其实是隐含一个递归思想的，然而这个思想被大多数人所熟知，那就是利用汉诺塔思想，
涉及到在01背包的最优解问题中，最优解是可以一步一步分成其子问题的最优解的。
子问题是包含于问题的，且解决方法是相同的。
注意，这里的拆分是一层一层的剥开，而不是一块一块的分开，后者是分治的思想。类似归并，快速排序
且这里假设子问题最优解已知，
问题（包括n个物品）- 部分 = 子问题（包括n-1个物品）；
部分即第n个物品存在与不存在的问题：
1、如果最优解里边存在第n个物品的话，那么子问题背包总重量限制将减去第n个物品总重量，而子问题最优解价值也将也将减去第n个物品的价值。
2、如果最优解里边__不存在__第n个物品的话那么子问题背包总重量限制与原来一样。
这个部分是选1还是选2 看两个条件：
一是当前问题的 重量限制能否放得下，如不能则直接进入选2；
二是如果能放下，刚判断1和2中（存在n与不存在n）子问题（n-1个物品）的价值哪个大，选出那个大的给来就反过来决定了选不选第n个物品。
另外，最内边层的子问题：第0个物品的价值是0，
#include <iostream>
int w[] = { 4,3, 7, 8, 9}; //weight
int v[] = { 5,4, 10, 11, 13}; //value
//第n个物品weight和value存储在w[n-1]和v[n-1]中
int c(int n, int wei)
{
if(n==0) return 0;
if(wei<w[n-1])
return c(n-1,wei);
else
return max( v[n-1] + c(n-1,wei-w[n-1]),c(n-1,wei));
}
int main()
{
std::cout << c(5,7) << std::endl;
return 0;
}
这是最原始的理解，可以看出，在大部分情况下，每次函数执行都会产生两次递归调用，时间复杂度为 O(2^n)
因为递归的方式要调用 2^n 次c，
而关于c的参数n，wei的组合只有n*wei种，
此时必定会有大量重复的递归，
现在进行优化：构造一个c关于n和wei的表格，对不同参数的n和wei的组合进行列表，这样就可以减少大量的运算。
//构造数组
int c[n+1][wei+1]，
//递归调用是从外向里进行调用的，而内层并不与外层相关。故从c[0][0]开始填表；
for(int i = 0; i <= n; i++)
{
for(int w = 0; w <= wei; w++)
{
if (i == 0) c[i][w] = 0;
else
{
if(w[i-1]>w ) c[i][w] = c[i-1][w];
else
{
c[i][w] = max(c[i-1][w],c[i-1][w-weight[i-1]]+value[i-1])
//对应上部分1和部分2，选取价值高的子问题。
//第i个物品weight和value存储在weight[i-1]和value[i-1]中
}
}
}
}
Comments