说明：算法来源于教材。 本文相当于关于教材的笔记(求解动态规划和贪婪算法的01背包，首先要按照单位重量的价格从大到小排序背包。 否则，分割的子问题不具有最佳子结构的性质) ) )。
动态规划算法：
动态计划是填表的过程。 此表记录了已解决子问题的答案。 上一个问题的答案在解决下一个问题时使用。 {例如01背包问题：假设有一个背包，背包容量为10，有5件物品，编号为1、2、3、4、5，各有重量和价格。 为了不超过背包的容量，要求将行李装载到背包中的价值最大化。 现在，将问题分割为五个子问题。
1 .从背容=10、1号中找到那个问题的答案
2 .从背影=10、1、2中找到该问题的答案
3 .从背容=10、1号、2号、3号中找到这个问题的答案
4 .从背容=10、1号、2号、3号、4号物品中找到这个问题的答案
5 .从背容=10、1号、2号、3号、4号、5号物品中找到这个问题的解
}
想法：
我们可以把对1、2、3、4、5个问题的答案都放在一张表上。 因为要解决2子问题，需要1子问题的解答。 第二个步骤方案与第一个步骤方案相比较，如何使第二个该步骤方案优于第一个相应方案。 2将此步骤标记为可执行。 不优于1或者不符合问题约束条件的，放弃该方案。 继续沿用与该步骤对应的第一方案作为该步骤的方案)。 解决3子问题需要2子问题的解答，解决5子问题需要4子问题的解答。 而且，五子问题是原来的问题。 5子问题的答案是最终原问题的解。
解决方法：
01以背包问题为例进行说明。 给出问题参数：
c=10； //背包容量cn=5； //物体个数nintw [6]={ 0，2，2，6，5，4 }； //物的重量w，0是没有意义的，只是为了便于说明问题的intp [6]={ 0，6，3，5，4，6 }； //物价p运行的最终结果不令人满意的未来表： (f[i][j]，I为n，j为c ) ) ) ) ) ) ) ) ) ) ) ) )。
关于n (c 012345678910000000000000000006620069993006991140069110113 14500669121515填表的说明：
1 .程序逐行填写。 f[0][0、1、2、3、4.f[5][0、1、2、3、4.] (程序初始化的过程是将第0行中的所有数填写为0，这符合现实。 这表明现在的背包里没有行李，现在的背包价值为0 )
用f[3][8]=11说明填写的过程。 f[3]表示i=3，f[3][*]的值是第三个子问题的解。 我选择的第3个项目的重量为6，其价值为5，所以找到与其前6列的前一行对应的背包的价值(f[2][2] )5(当前选择的第3个项目的价值)=11，值为11f[2][8]=9 代表性地说，我选择的1，3的方案需要把1，9填在表上-------------在这里，说明f[2][8]=9的意思。 两个子问题的一个解是，{ 1，2 }对应于1，2号物品的背包价值为9。 ------------碰巧我们在解决三个问题时，{1、2、3}需要计算和比较这些方案。 1、2号物品{1、2}背价=？ 背包的价格是多少，{ 1，3 }背包的价格=？{1、2、3}背价=？ 另一方面，{ 1，2 }背包的价格已经在2子问题中列出，可以直接在3子问题中使用。 为什么不考虑{ 2，3 }？ 是2号和3号组队放在背包里吗？ 因为，对于两个子问题，已经有这样的问题：【如果选择一个背包，选择第一个背包所获得的价值大于选择第二个背包所获得的价值---我们追溯到f[2][2]=6，当背包的容量为2时，[ 因此，挪用前面子问题的解作为该步骤的答案。 因此，f[2][2]是6而不是3。 因此，这相当于在解决以下子问题的同时，如果背包中有只能从2号和1号中选择一个的话，请选择1号。
3 .实际上，在编码上述描述时，会加上两层for循环(遍历n，进而嵌套遍历c )和两个判断)1.当前子问题的一个可行方案和上一个子问题的相应可行方案是谁2 .连续变量j的值达到跳转点的值，是否值得只有达到才更新当前背包) :代码如下
# include iostream # include stdio.husingnamespacestd； voidknapsack(intn，int c，int *w，int *p ) { int f[100][100]； int i=0，j=0； for(I=1； i=n； I ) for(j=1； j=c； j({f[I][j]=f[I-1][j]； if(j=w(I ) ) f (I ) ) j ) ) max ) f ) I-1 ) ) j-w (I ) ) p ) I ) )； }//因为我是I
和j++，循环结束，多加了一次i和j，所以最后要减回来 cout<<"背包能装的最大价值是：" << f[i-1][j-1] <<endl;}int main(){ int n; int c; /* int w[100]; int p[100]; cout << "请输入背包容量c："<< endl; cin >>c; cout <<"请输入物体个数n："<<endl; cin >>n; for(int i=1;i<=n;i++) { cout<<"请输入物重w["<<i<<"]："<<endl; cin >> w[i]; } for(int i=1;i<=n;i++) { cout<<"请输入物价p["<<i<<"]："<<endl; cin >> p[i];}*/c=10; //背包容量cn=5; //物体个数nint w[6]={0,2,2,6,5,4}; //物重w int p[6]={0,6,3,5,4,6}; //物价p Knapsack(n,c,w,p);}如何进一步优化算法：
上述算法有两个明显的缺点:
其一是算法要求所给物品的重量w[i]是整数.
其次，当背包容量很大时，算法需要的计算时间较多，当c>2^n,算法需要n*2^n这么多的计算时间.
优化思路：
仔细观察，发现该二维表的值，是关于物品背包当前背包容量的阶梯状函数，并且它是一个阶梯状，单调不减函数，所以我们可以通过构造跳跃点集的方式来优化算法。其相关说明如下：
程序运行的数据流图如下：
最后放一下优化后的算法的代码实现：
#include<iostream>using namespace std;template<class Type> //void Traceback(int n, Type w[], Type v[], Type **p,int *head) {void Traceback(int n, Type w[], Type v[], Type p[][2],int *head) { int x[n+1];Type j = p[head[0] - 1][0], m = p[head[0] - 1][1];for (int i = 1; i <= n; i++) {x[i] = 0;for (int k= head[i+1]; k<=head[i]-1; k++){if(p[k][0]+w[i]==j && p[k][1]+v[i]==m) {x[i]= 1; j=p[k][0]; m= p[k][1]; break;}}}//cout<<x[n];}template<class Type> Type Knapsack(int n, Type c, Type v[], Type w[]) {//int **p=new int*[100];//行数//for(int i=0;i<100;i++){p[i]=new int[2];}int p[100][2];int head[7];//int *head = new int[n + 2];head[n + 1] = 0;p[0][0] = 0;p[0][1] = 0;int left = 0, right = 0, next =1;head[n] = 1;//w=[2,2,6,5,4] <----------五个物品，循环取五次。//v=[6,3,5,4,6] <----------程序取物品是5号，4号，3号的顺序//第一次：left=1，right=2，head[4]=next=3//依次找出子问题的活跃点集（{5}，{5，4}，{5,4,3},{5,4,3,2},{5,4,3,2,1}备注：5，4，3，2，1是物品的标号）//1号循环for (int i = n; i >= 1; i--) {int k = left;//第一次循环next=3，left=0；right=2；=====>第二次left=1，right=2，next=5//p[2][0]=4/6//第一次循环next=3，left=0；right=2；//p[2][0]=4/6 =========>第二次p[4][0]=4/6 //2号循环for (int j = left; j <= right; j++) {if (p[j][0] + w[i] > c) break;Type y = p[j][0] + w[i], m = p[j][1] + v[i];//数组应该足够大，否则会数组越界，运行到该处，程序会死循环//将此步的方案差于上一步方案，则用上一个方案取代该方案，做为该步的答案//循环几次，就为当前子问题新增多少个活跃点集（在当前方案差于上一方案的前提下会循环）while (k <= right && p[k][0]<y) {p[next][0] = p[k][0];p[next++][1] = p[k++][1];}if (k <= right && p[k][0] == y) { if(m<p[k][1]) m= p[k][1]; k++;}//在2号循环的带动下，循环几次，就为当前子问题新增多少个活跃点集（在当前方案优于上一方案的前提下会循环）//当前方案优于上一步的方案？，（更新表）将当前方案放入表中if (m > p[next - 1][1]) {p[next][0] = y;p[next++][1] = m;}while (k <= right && p[k][1] <= p[next - 1][1])k++;}while (k <= right) {//第一次是将p[2][0]=4/6赋给p[4][0]=4/6p[next][0] = p[k][0];p[next++][1] = p[k++][1];}left = right + 1;right = next - 1;head[i - 1] = next;}Traceback(n, w, v, p, head);//cout <<"bset price："<< c;return p[next - 1][1];}int main(){int w[11]={0,2,2,6,5,4};int v[11]={0,6,3,5,4,6};//int **p=new int[][2];int c=Knapsack(5,10,v,w);//int w[7]={0,2,3,4,5};//int v[7]={0,3,4,5,6};//int c=Knapsack(4,8,v,w);cout <<"best price："<< c;//cout <<"best price："<< c;}后记：
算法的时间复杂度分析： 优化前：O（nc） 优化后：O（min{nc，2^n}）
上述问题不知道我描述清楚否，记录的是否有误。欢迎在评论区留言。我们一起学算法