动态规划法求解0/1背包问题 C语言

本文主要是介绍动态规划法求解0/1背包问题 C语言，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。

在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, …, xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。

基本思路：

0/1背包问题，首先判断当前背包容量是否可以容纳该物品，如果背包重量超过当前背包容量就不可以放入，如果小于则需要进一步判断，假设当前物品为i,重量为wj,则取前i-1个物品装入容量为j的背包的价值和前i-1个物品装入容量为j-wj的背包加上物品i的价值的最大值。

按照这样的思路，填写过程表格，背包最大价值就是过程矩阵最后一个元素的值。最后倒推求出是哪些物品。

程序清单：

#include<stdio.h>/*结构体 物品*/
struct Goods
{int id;				//物品编号int is_in_bag;		        //当前物品是否在背包中，1表示在背包，0表示不在int weight;			//当前物品的重量int value;			//当前物品的价值
}goods[50];                             //目前所支持最大物品数量为50，可根据实际情况调整/*函数原型声明*/
int KnapSack(struct Goods goods[50] ,int n,int C);	//求背包的最大价值
void PrintInfo(struct Goods goods[50],int n);		//输出物品信息
void IsInBagInfo(struct Goods goods[50],int n);		//装入背包中的物品的信息/*主函数*/
int main()
{int i;int capacity;		//背包的容量int goods_number;	//物品的个数int max_value;		//最大价值/*输入背包容量、物品个数、物品重量、物品价值*/printf("请输入背包容量:");while(scanf("%d",&capacity) != EOF){	printf("请输入物品的个数:");scanf("%d",&goods_number);while(goods_number > 50){printf("抱歉，当前所容许最大物品数量为50，请您重新输入");scanf("%d",&goods_number);}printf("请输入%d物品的重量:",goods_number);for(i=0;i<goods_number;i++){goods[i].id=i+1;goods[i].is_in_bag=0;//默认表示当前物品不在背包scanf("%d",&goods[i].weight);}printf("请输入%d个物品的价值:",goods_number);for(i=0;i<goods_number;i++){scanf("%d",&goods[i].value);}/*输出用户输入的信息*/PrintInfo(goods,goods_number);/*求最大价值*/max_value=KnapSack(goods,goods_number,capacity);/*输入背包中物品的信息*/IsInBagInfo(goods,goods_number);/*输出最大价值*/printf("\n最大价值为%d",max_value);/*开始下一次计算*/printf("\n\n\n请输入背包容量");}return 0;
}/*输出物品信息*/
void PrintInfo(struct Goods goods[50],int n)
{int i=0;printf("--------------------------------------------------------\n");printf("您输入的物品信息如下:\n");printf("\n物品ID\t重量\t价值\n");for(i=0;i<n;i++){printf("%d\t%d\t%d\n",goods[i].id,goods[i].weight,goods[i].value);}
}/*求背包的最大价值*/
// n——n个物品
// C——背包容量为C
int KnapSack(struct Goods goods[50] ,int n,int C)
{int i,j;int V[50][50]={0};	//存放迭代结果//初始化第0列for(i=0;i<=n;i++)	{V[i][0]=0;}//初始化第0行for(j=0;j<=C;j++)	{V[0][j]=0;}//分别计算每一行for(i=1;i<=n;i++){for(j=1;j<=C;j++){if(j<goods[i-1].weight) //物品重量大于背包重量，不能放入V[i][j]=V[i-1][j];else					//物品重量小于等于背包重量{V[i][j]=(V[i-1][j]>V[i-1][j-goods[i-1].weight]+goods[i-1].value)?V[i-1][j]:V[i-1][j-goods[i-1].weight]+goods[i-1].value;}}}//求装入背包的物品for(j=C,i=n;i>0;i--){if(V[i][j]>V[i-1][j]){goods[i-1].is_in_bag=1;j=j-goods[i-1].weight;}else{goods[i-1].is_in_bag=0;}}//输出计算过程printf("--------------------------------------------------------\n");printf("计算过程如下:\n");for(i=0;i<=n;i++){for(j=0;j<=C;j++)printf("%3d",V[i][j]);printf("\n");}//返回背包最大价值return V[n][C];
}/*输出装入背包中的物品的信息*/
void IsInBagInfo(struct Goods goods[50],int n)
{int i=0;printf("--------------------------------------------------------\n");printf("背包中的物品为:\n");printf("物品ID\t重量\t价值\n");for(i=0;i<n;i++){if(goods[i].is_in_bag==1)printf("%d\t%d\t%d\n",goods[i].id,goods[i].weight,goods[i].value);}
}

参考结果：