[C语言]背包问题「建议收藏」

[C语言]背包问题「建议收藏」0-1背包问题 参考:http://blog.csdn.net/liwenjia1981/article/details/5725579http://blog.csdn.net/dapengbusi/article/details/7463968动态规划解法借个图助于理解从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4

大家好,又见面了,我是你们的朋友全栈君。

0-1背包问题

 

参考:

http://blog.csdn.net/liwenjia1981/article/details/5725579

http://blog.csdn.net/dapengbusi/article/details/7463968

动态规划解法

借个图 助于理解

[C语言]背包问题「建议收藏」

从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,….10的时候,最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候,最佳方案还是上一排的最价方案c为4.而背包容量为5的时候,则最佳方案为自己的重量5.背包容量为7的时候,很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

#include<stdio.h>

int f[10][100];
//构造最优矩阵
void package0_1(int *w,int *v,int n,int c)
{
	int i,j;
	//初始化矩阵
	for(i=1;i<=n;i++)
		f[i][0] = 0;
	for(j=1;j<=c;j++)
		f[0][j] = 0;	
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=c;j++)
		{
			//当容量够放入第i个物品,并且放入之后的价值要比不放大
			if(w[i] <= j && f[i-1][j-w[i]] + v[i] > f[i-1][j])
			{
				f[i][j] = f[i-1][j-w[i]] + v[i];			
			}else
				f[i][j] = f[i-1][j];
		}
	}	
	printf("最大价值: %d \n",f[n][c]);
}

//构造最优解
void getResult(int n,int c,int *res,int *v,int *w)
{
	int i,j;
	j = c;
	for(i=n;i>=1;i--)
	{
		if(f[i][j] != f[i-1][j])
		{
			res[i] = 1;
			j = j - w[i];
		}
	}
}

void main()
{
	int w[6] = {0,2,2,6,5,4};//每个物品的重量
	int v[6] = {0,6,3,5,4,6};//每个物品的价值
	int res[5] = {0,0,0,0,0};
	int n = 5; //物品的个数
	int c = 10; //背包能容的重量
	int i,j;
	package0_1(w,v,n,c);
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=c;j++)
			printf("%2d ",f[i][j]);
		printf("\n");
	}
	getResult(n,c,res,v,w);
	printf("放入背包的物品为: \n");
	for(i=1;i<=n;i++)
		if(res[i] == 1)
			printf("%d  ",i);
}

0-1背包的递归解法

#include<stdio.h>

int maxNum[6];  //存放最优解的编号
int maxValue=0; //存放最大价值
int w[6] = {0,2,2,6,5,4};//每个物品的重量,第一个为0,方便角标对应
int v[6] = {0,6,3,5,4,6};//每个物品的价值,第一个为0,方便角标对应
int num = 5; //物品的个数  
int cap = 10; //背包能容的重量   

void package01(int *flag,int n,int c,int nowValue)
{
	int i;
	if(n == 0 || c == 0)
	{
		if(nowValue > maxValue)
		{	
			for(i=0;i<6;i++)
				maxNum[i] = flag[i]; 
			maxValue = nowValue;
		}
		return;
	}
	
	if(c >= w[n])
	{
		flag[n] = 1;
		package01(flag, n-1, c-w[n], nowValue+v[n]);
	}
	flag[n] = 0;
	package01(flag, n-1, c, nowValue);	
}

void main()
{
    int flag[6] = {0,0,0,0,0,0};  
    int i;  
    package01(flag,num,cap,0);  
	for(i=1;i<=num;i++)
		maxNum[i] == 1 ? printf("第%d号货物装了包中  \n",i) : 0;
	printf("最大价值为:%d  \n",maxValue);
}

 

 完全背包问题

与0-1背包问题区别在每个物品有无限多个。

#include<stdio.h>   

int f[10][100];  
//构造最优矩阵   
void package0_1(int *w,int *v,int n,int c)  
{  
    int i,j,k;  
    //初始化矩阵   
    for(i=1;i<=n;i++)  
        f[i][0] = 0;  
    for(j=1;j<=c;j++)  
        f[0][j] = 0;      
	
    for(i=1;i<=n;i++)  
    {  
        for(j=1;j<=c;j++)  
        {  
            //当容量够放入k个第i个物品,并且放入之后的价值要比不放大   
			k = j/w[i];
            if( k>0 && (f[i-1][j- k * w[i]] +  k * v[i] > f[i-1][j]))  
            {  
				f[i][j] = f[i-1][j- k * w[i]] +  k * v[i] ;         
            }else  
                f[i][j] = f[i-1][j];  
        }  
    }     
    printf("最大价值: %d \n",f[n][c]);  
}  

//构造最优解   
void getResult(int n,int c,int *res,int *v,int *w)  
{  
	int i,j;  
	j = c;  
	for(i=n;i>=1;i--)  
	{  
		while(f[i][j] > f[i-1][j])  
		{  
			res[i] ++;  
			j = j - w[i];  
		}  
	}  
}  

void main()  
{  
    int w[6] = {0,4,6,6,3,6};//每个物品的重量   
    int v[6] = {0,1,1,1,2,1};//每个物品的价值   
    int res[5] = {0,0,0,0,0};  
    int n = 5; //物品的个数   
    int c = 10; //背包能容的重量   
    int i,j;  
    package0_1(w,v,n,c);  
    for(i=0;i<=n;i++)  
    {  
        for(j=0;j<=c;j++)  
            printf("%2d ",f[i][j]);  
        printf("\n");  
    }  
	getResult(n,c,res,v,w);  
    printf("放入背包的物品为: \n");  
    for(i=1;i<=n;i++)  
		if(res[i] >= 1)  
			printf("放入了第%d号物品%d个\n  ",i,res[i]);  
}  

 

部分背包问题

与0-1背包的区别:装入的可以不是整个装入,理解为“装沙”。其余要求一样。

用贪心法求解

#include<stdio.h>   

void package_part(int *w,int *v,double *p,int n,int c,int *flag)  
{  
    int i,j,temp;
	double tempD,totalValue = 0.0;
	
	//计算单价
	for(i=0;i<n;i++)
	{
		p[i] = (double)v[i] / (double)w[i];
		flag[i] = i;
	}
	//根据单价排序,flag数组保存物品的下标
	for(i=0;i<n;i++)
	{
		for(j=n-1;j>i;j--)
		{
			if(p[j] > p[j-1])
			{
				temp = flag[j];
				flag[j] = flag[j-1];
				flag[j-1] = temp;	
				
				tempD = p[j];
				p[j] = p[j-1];
				p[j-1] = tempD;
			}
		}
	}
	//贪心法得出应该装入的物品	
	for(i=0;i<n;i++)
	{
		if(c >= w[flag[i]])
		{
			totalValue += v[flag[i]];
			c -= w[flag[i]];
			printf("第%d号物品整个放入\n",flag[i]);
		}else
		{
			totalValue += p[flag[i]] * (double)c / (double) w[flag[i]];
			printf("第%d号物品放入了%f\n",flag[i],(double)c / (double) w[flag[i]]);
			break;
		}
	}
	printf("总价值为:%f",totalValue);
}  

void main()  
{  
    int w[5] = {4,6,6,3,6};//每个物品的重量   
    int v[5] = {1,1,1,2,1};//每个物品的价值   
    double p[5] = {0,0,0,0,0};//每个物品的单位价值  
	int flag[5]; //用于排序
    int n = 5; //物品的个数   
    int c = 10; //背包能容的重量   
    package_part(w,v,p,n,c,flag);  
}  

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159118.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java urlencoder,java中的URLEncoder和URLDecoder类「建议收藏」

    java urlencoder,java中的URLEncoder和URLDecoder类「建议收藏」java中的URLEncoder和URLDecoder类URLEncoder类包含将字符串转换为application/x-www-form-urlencodedMIME格式的静态方法。为了解决web设计中不同操作系统间的差异性,我们在URL中使用的字符就必须是一个ASCII字符集的固定字集中的元素,具体如下:1.大写字母A-Z2.小写字母a-z3.数字0-94.标点符-_.!~…

  • Java开发手册之模块命名「建议收藏」

    Java开发手册之模块命名「建议收藏」Java开发手册之模块命名

  • densenet详解_dense参数

    densenet详解_dense参数DenseNet于论文《》中提出,是CVPR2017的oral。论文提出DenseNet并与ResNet和Inception做对较。为提升网络的效果,一般操作是增加网络的深度和宽度,但论文作者另辟蹊径,聚焦于feature的极致利用以获得更佳效果和更少参数。对于梯度消失问题,ResNet等网络使用跳层连接结构加以解决。作者延续该思路,提出DenseBlock,在保证网络层间最大程度的信息传输的同时,直接将所有层连接起来。……………………

  • 最全面、最详细web前端面试题及答案总结

    2021最全面、最详细web前端面试题及答案总结总结不易,希望可以帮助到即将面试或还在学习中的web前端小伙伴,祝面试顺利,拿高薪!本章是HTML考点的⾮重难点,因此我们采⽤简略回答的⽅式进⾏撰写,所以不会有太多详细的解释。我们约定,每个问题后我们标记『✨』的为⾼频⾯试题doctype的作⽤是什么?✨DOCTYPE是html5标准⽹⻚声明,且必须声明在HTML⽂档的第⼀⾏。来告知浏览器的解析器⽤什么⽂档标准解析这个⽂档,不同的渲染模式会影响到浏览器对于CSS代码甚⾄JavaScript

  • pytorch安装以及pycharm使用pytorch包(windows10)

    pytorch安装以及pycharm使用pytorch包(windows10)1.安装anacondahttps://www.anaconda.com/products/individual#windows在该网站上下载anaconda的包,然后使用默认设置安装即可。为anaconda配置环境变量anaconda和miniconda同为conda官方推荐的conda工具。anaconda和conda的关系,就像github和git的关系,anaconda不光包含了conda命令行软件,还包含了多如牛毛的预装python包,以及令人瞠目结舌的黑科技全家桶。win+R打开

  • DHCP协议原理及其实现流程

    DHCP协议原理及其实现流程DHCP(Dynamic Host Configuration Protocol):动态主机配置协议在常见的小型网络中(例如家庭网络和学生宿舍网),网络管理员都是采用手工分配IP地址的方法,而到了中、大型网络,这种方法就不太适用了。在中、大型网络,特别是大型网络中,往往有超过100台的客户机,手动分配IP地址的方法就不太合适了。因此,我们必须引入一种高效的IP地址分配方法,幸好,DHCP(Dy

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号