当前位置:   article > 正文

贪心算法解决背包问题和动态规划解决0-1背包问题(c语言)_背包问题贪心算法c语言

背包问题贪心算法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);

	
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

运行结果如下:
在这里插入图片描述

动态规划求解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");

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

运行结果如下:

在这里插入图片描述

总结:

贪心算法:

每一步都做出当时看起来最佳的选择,也就是说,它总是做出局部最优的选择。

贪心算法的设计步骤:

  1. 对其作出一个选择后,只剩下一个子问题需要求解。
  2. 证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安全的。
  3. 剩余子问题的最优解与贪心选择组合即可得到原问题的最优解。

动态规划:

应用于子问题重合的情况,不同的子问题具有相同的子子问题,

动态规划算法将每个子问题求解一次,将其解保存在一个表格中,需要时进行调用。

  1. 刻画一个最优解的结构特征。
  2. 递归的定义最优解的值。
  3. 计算最优解的值,有自顶向下和自底向上的方法,通常采用自底向上的方法。

贪心算法和动态规划算法的区别:

1.贪心:每一步的最优解一定包含上一步的最优解,上一步之前的最优解则不作保留;

动态规划:全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有的局部最优解 。

2.动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常自顶向下的方式进行。

3.根据以上两条可以知道,贪心不能保证求得的最后解是最佳的,一般复杂度低;而动态规划本质是穷举法,可以保证结果是最佳的,复杂度高。

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/767824
推荐阅读
相关标签
  

闽ICP备14008679号