0/1背包问题---C++动态规划法

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

【问题】

给定n种物品和一个背包物品i1≤i≤n的重量是其价值为背包容量为对于每种物品只有两种选择装入背包或者不装入背包。如何选择装入背包的物品使得装入背包中物品的总价值最大

【想法】

首先证明0/1背包问题满足最优性原理。

设是0/1背包问题的最优解则是下面子问题的最优解

其中要找到

如若不是子问题最优解则在子问题必然有一个最优解的前提下设是上述子问题的一个最优解则且。因此这说明是0/1背包问题的最优解且比更优从而导致矛盾。

用0、1表示的装入与否设表示将n个物品选择性装入容量为C的背包中所获得的最大值。显然初始子问题是把前面i个物品装入容量为0的背包和把0个物品装入到容量为j的背包中此时的V值均是0

我们在选择装入时通常遇到两种情况

一是背包容量足够大此时自然是装入的物品越多价值越大尽管没有这样的背包

二是背包容量有限我们需要对n件物品进行筛选选择性价比最高的一种装入方法而且背包的容量要接近100%使用。

那么会有一下两种状况

当我们装到一定程度时发现背包剩余容量不足以装入第i件物品那么选择装入第i件物品是的最大价值与选择装入第i-1件物品的最大价值是相同的
背包容量可以装第i件物品那么装入背包价值等于一个拥有容量的背包在i-1件物品中选择是否装入+第i个物品的价值如果没有装入第i个物品那么背包中物品的价值等于一个容量为j的背包在i-1件物品中选择装入的价值显然取二者中价值最大的作为最优解。于是有以下递推式;

接着要确定背包装入了哪些物品得从后往前推如果V(n,C)>V(n-1,C)表明第n个物品被装入将第n个物品踢出得到一个容量为的背包选择n-1个物品否则则是一个容量为C的背包选择n-1个物品以此类推直到确定第一个物品的装入与否。由此得到如下函数

例如有5个物品其重量分别是{2,2,6,5,4}价值分别为{6,3,5,4,6}背包容量为10用动态规划法求解0/1背包问题过程如图表所示动态规划法的核心就是建立图表

【算法实现】

#include<iostream>
using namespace std;
#include<cmath>
#include<string>
int V[6][11];
int x[5];
int max(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;	
} 
int KnapSack(int w[],int v[],int n,int C)
{
	int i,j;
	for(i=0;i<=n;i++)//初始化第0列 
		V[i][0]=0;
	for(j=0;j<=C;j++)//初始化第0行 
		V[0][j]=0;
	for(i=1;i<=n;i++)//计算第i行进行第i次迭代 
	{
		for(j=1;j<=C;j++)
		{
			if(j<w[i-1])
				V[i][j]=V[i-1][j];
			else
				V[i][j]=max(V[i-1][j],V[i-1][j-w[i-1]]+v[i-1]);
		}
	}
	for(i=n,j=C;i>0;i--)//求装入背包的物品 
	{
		if(V[i][j]>V[i-1][j])
		{
			x[i-1]=1;
			j=j-w[i-1];
		}
		else
			x[i-1]=0;
	}
	return V[n][C];//返回背包取得的最大价值 
}
int main()
{
	int w[5]={2,2,6,5,4};
	int v[5]={6,3,5,4,6};
	cout<<"背包最大价值是"<<KnapSack(w,v,5,10)<<endl;
	cout<<"装入的物品分别是"; 
	for(int i=0;i<5;i++)
	{
		if(x[i]==1)
			cout<<"物品"<<i+1<<'\t';
	}
	return 0; 
}