动态规划算法解01背包问题（思路及算法实现）

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

说明：算法源自教材。本文相当于对教材做的一个笔记(动态规划与贪心算法解01背包必须先对背包按照单位重量的价格从大到小排序，否则拆分的子问题就不具备最优子结构的性质)

动态规划算法：
    动态规划就是一个填表的过程。该表记录了已解决的子问题的答案。求解下一个子问题时会用到上一个子问题的答案。{比如01背包问题：假如有1个背包，背包容量是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的每一步方案比较，如何2的该步方案优于1所对应的方案。则将2的这步方案标为可行。如果不优于1的，或者不满足问题的约束条件，则舍弃该方案。继续沿用该步所对应的1的方案作为该步的方案)。求解3子问题，需要用到2子问题的答案，一直递推到求解5子问题，需要用到4子问题的答案。而5子问题就是原问题。5子问题的答案就是最终原问题的解。
 

解法：

       以01背包问题为例，作讲解。给出问题参数：

	c=10;   //背包容量c
	n=5;    //物体个数n
	int w[6]={0,2,2,6,5,4};   //物重w,0无意义，只是为方便描述问题而已
    int p[6]={0,6,3,5,4,6};   //物价p 

运行的最终结果是张二维表：（f[i][j],i就是n，j就是c）

填表相关说明：

1.程序是一行一行的进行填表的。f[0][0,1,2,3,4…..]……f[5][0,1,2,3,4….]  (程序初始化的过程就是将第0行的所有数填为0，这是符合现实情况的。它表明当前背包没有装物品，当前背包的价值是0)

2.拿f[3][8]=11来说明填表的过程。f[3]表明i=3(当前子问题有3个物品可选，分别是1，2，3号物品)，f[3][*]的值就是第3个子问题的解。我要选的3号物品的重量是6，它的价值是5，所以我会找到它的前6列的上一行所对应的背包的价值（f[2][2]）+5（当前要选的3号物品的价值）=11,值为11>f[2][8]=9，代表我选了1,3的方案要优于选1，2的这种方案，所以我将11填入到表格【如果f[2][2]+5<9,则将9填入表格】——————-这里需要说明一下f[2][8]=9的含义：2子问题的一个解是{1，2}选择1，2号物品所对应的背包价值为9。——恰巧我们在解决3子问题时{1，2，3}需要计算比较这几种方案，选1，2号物品{1，2}>>>>背价=？，背包价格是多少，{1，3}>>>>背价=？,{1，2,3}>>>>背价=？而{1,2}>>背包价格在2子问题中已给出，因此我们可以在3子问题中直接用。为何不考虑{2，3}呢？就是拿2号和3号组队放入背包？因为在2子问题中已经记载了：【如果要单选一个背包的话，选择1号获得的价值要比2号获得的价值大—-我们追溯到f[2][2]=6是整么来的，背包容量是2的时候，[1,2]号物品只能有一个放入背包，放入1，背包的价值是6，f[1][2]=6的计算是在1子问题中已经求解出来的，2子问题可以直接用该值，而不用再重复计算。放入2号，背值是3，3<6,所以沿用上一个子问题的解作为该步的答案，所以f[2][2]是6，而不是3，所以它相当于定义说：下一个子问题在求解的过程中，如果遇到只能从2号和1号物品中选择一个物品装入背包时，请选择1号物品】

3.其实将上述的描述写成代码，就是两层for循环（遍历n，再嵌套遍历c），加上两个判断（1.当前子问题的可行的一个方案与上一个子问题的对应的可行方案谁最优。2.连续变量j的值是否达到了跳跃点的值，达到了才更新当前背包的价值）：代码如下

#include<iostream>
#include<stdio.h>
using namespace std;

void Knapsack(int n,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],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;   //背包容量c
		n=5;    //物体个数n
		int 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/6
				p[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}）

     上述问题不知道我描述清楚否，记录的是否有误。欢迎在评论区留言。我们一起学算法