贪心算法解决背包问题和动态规划解决0-1背包问题（c语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了贪心算法解决背包问题和动态规划解决0-1背包问题（c语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

贪心算法解决背包问题（c语言）

#include<stdio.h>
struct goods{
	int w;//商品重量
	int p;//商品价值
	double avg;//单位商品的价值
};


double beibao(goods g[],int c,int N,double X[]){
	double v=0;
	for(int i=0;i<N;i++){
		if(c<g[i].w){
			if(c>0){
				X[i]=(double)c/(double)g[i].w;
				v=v+c*g[i].avg;
				c=0;
			}else break;
		}else{
			v=v+g[i].p;
			c=c-g[i].w;
			X[i]=1;
		}
	}
	return v;
}
void sort(goods g[],int N){
	for(int i=0;i<=N-1;i++){
		for(int j=0;j<=N-1-i;j++){
			
			if(g[j].avg>g[++j].avg){
				goods x;
				x=g[j];
				g[j] =g[++j];
				g[++j] =x;
			}
		}
	}
}
void main(){
	int N=3;
	double X[3]={0,0,0};
	goods g[3];
	printf("请输入背包的重量：");
	int c;
	scanf("%d",&c);
	for(int i=0;i<N;i++){
		printf("请输入第%d个商品的重量：",i+1);
		scanf("%d",&g[i].w);
		printf("请输入第%d个商品的价值:",i+1);
		scanf("%d",&g[i].p);
		g[i].avg=(double)g[i].p/(double)g[i].w;
	}
	sort(g,N);
	double v=beibao(g,c,N,X);
	for (int j=0;j<N;j++){
		printf("第%d个商品: %d,%d\n",j+1,g[j].w,g[j].p);
	}
	printf("解向量为：\n");
	for(int k=0;k<N;k++){
		printf("%f\n",X[k]);
	}
	printf("价值最大为:%f",v);

	
}

运行结果如下：
c语言贪心算法解决该背包问题,贪心算法,动态规划,c语言

动态规划求解0-1背包问题（c语言）

#include<stdio.h>
void main(){
int w[3]={3,2,4}; //物品重量
int p[3]={5,3,6}; //物品价值
int x[4][7];
int Z=6; //背包的总重量
for(int i=0;i<=6;i++){
	x[0][i]=0;
}
for(int j=0;j<=3;j++){
	x[j][0]=0;
}
//填表
for(int m=1;m<=3;m++){
	for(int n=1;n<=6;n++){
		if(w[m-1]>n)
			x[m][n]=x[m-1][n];
		else{
			int value1=x[m-1][n];
			int value2=x[m-1][n-w[m-1]]+p[m-1];
			if(value2>value1)
				x[m][n]=value2;
			else
				x[m][n]=value1;
		}
	}
}
//打印表
for(int c=0;c<=3;c++){
	for(int d=0;d<=6;d++){
		printf("%3d",x[c][d]);
}
	printf("\n");
}

int q[3]={0,0,0}; //选取方案，选了则为1，不选则为0
int l=6;
for(int k=3;k>=0;k--){
		if(x[k][l]==x[k-1][l]){
			q[k-1]=0;
		}else if(x[k][l]==x[k-1][l-w[k-1]]+p[k-1]&&j-w[k-1]>=0){
			q[k-1]=1;
			l=l-w[k-1];
		}
	}

printf("总价值最大为:%d\n",x[3][6]);
//选取方案
printf("选取方案为（0代表该物品未选择，1代表该物品被选择）:\n");
for(int v=0;v<3;v++){
	printf("%3d",q[v]);
}
printf("\n");

}