01pack.cpp

01背包问题,用动态规划实现的,里面讲得很详细

//0-1背包
#include<iostream>
#include<iomanip>
using namespace std;

void KNAPSACK_DP(int n,int W);//构造最优解表函数
void OUTPUT_SACK(int c[][50],int j);//求装入背包的物品函数

    int c[50][50];//构造表数组
    int w[10];//重量数组
    int v[10];//价值数组
    int n;//物品个数
	int m;// 背包容量
	int x[10];//最优解数组

int main(){

	int i,k,j;
	cout<<"请输入物品的个数:"<<endl;//输入物品的个数
	cin>>n;
	cout<<"请输入各物品的重量:"<<endl;//输入各物品的重量
	for(i=1;i<=n;i++)
		cin>>w[i];
	cout<<"请输入各物品的价值:"<<endl;//输入各物品的价值
	for(i=1;i<=n;i++)
		cin>>v[i];
	cout<<"请输入背包的容量:"<<endl;//输入背包的容量
	cin>>m;
	KNAPSACK_DP(n,m);//调用构造最优解表函数
	cout<<"构造的最优解表:"<<endl;//输出最优解表
    cout<<"   c";
	for(i=0;i<=m;i++)
		cout<<setw(4)<<i;
	cout<<endl;
	for(k=1;k<=5;k++)
{ 
		cout<<setw(4)<<k;
   for(j=0;j<=m;j++) //
    cout<<setw(4)<<c[k][j]; 
    cout<<endl;
} 
	OUTPUT_SACK(c,m);//调用递推装入背包的物体函数
	cout<<"最优解＝:";
	for(i=1;i<=n;i++)//输出最优解
		cout<<setw(4)<<x[i];
	    cout<<endl;
		cout<<"最大价值="<<c[n][m]<<endl;//输出最大价值
    return 0;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
void KNAPSACK_DP(int n,int W)//构造最优解表
{
	int i,j;
	for(j=0;j<=W;j++)//初始化第0行
		c[0][j]=0;
	for(i=1;i<=n;i++)
	{
		c[i][0]=0;//第0列置0，即W＝0时，C＝0
		for(j=1;j<=W;j++)//计算C[i][j]
		{
			if(w[i]<=j)
			{
				if(v[i]+c[i-1][j-w[i]]>c[i-1][j])//判断是否得到更大值
					c[i][j]=v[i]+c[i-1][j-w[i]];//是则赋给c[i][j]
                else 
                   c[i][j]=c[i-1][j];//否则将原来的最大值赋给c[i][j]
			}
			else
				c[i][j]=c[i-1][j];//w[i]>j时将原来的最大值赋给c[i][j
		}
	}

}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
void OUTPUT_SACK(int c[][50],int j)//递推装入背包的物体
{   
//	char **pm = c ; //错误：从char (*)[5]到 char **的赋值
int (*pm5)[5] ;
pm5 = c ; //正确。
	int i;
	for(i=n;i>=2;i--)//物品个数从大到小，直至2个时
	{
		if(c[i][j]==c[i-1][j])//判断装入i个物品与i-1个物品时，最大价值是否相等
			x[i]=0;//是则赋0，即不放入包
		else
		{
			x[i]=1;//否则赋1，即放入包
			j=j-w[i];//减去放入包的第i个物品的重量
		}
	}
	x[1]=c[1][j]?1:0;//判断第1个物品是否放入包

}