本文欢迎转载，转载请注明：转载自中国学网： []
用户还关注
可能有帮助遗传算法的0-1背包问题(c语言)问题,背包,C,遗传算法的,c语言,C语言..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
遗传算法的0-1背包问题(c语言)
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口c语言程序设计 c语言 灌篮高手全国大赛 新浪爱问共享资料 工业设计 网球王子全国大..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
C语言程序设计大赛资料
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口&&问题点数：0&&回复次数：36&&&
[C语言编程接龙竞赛]第二题 背包问题
背包问题相信学过算法的都不陌生，有很多种背包的模型，今天我们的背包问题是这样的：小A有一个背包，他要背着它去野营，背包的容积是V，也就是说背包最多能装总体积为V的物品，假设现在已经有K种物品小A能够装进背包，每种物品都有它的体积，求出小A的背包能够装的物品的最大总体积为多少输入第一行:背包体积V 和物品数量K接下来K行：每个物品对应的体积v每个输入均为整数(其中V&=1000,K&=50)
竞赛时间：现在~11月6日
（题有点难，时间就定长一点)
竞赛事项：
[此贴子已经被作者于 16:30:33编辑过]
搜索更多相关主题的帖子:
&&&&&&&&&&
等　级：贵宾
威　望：35
帖　子：916
我觉得吧，搂主要把题目描述的更详细一点。这道题就不如上一道题，如n!清楚。我没看过很深奥的算法，是不是就不能参加这题目了呢？背包的容积是V，也就是说背包最多能装总体积为V的物品求出小A的背包能够装的物品的最大总体积为多少
等　级：贵宾
威　望：40
帖　子：10385
专家分：298
欢迎参加，我特别欢迎C++Coder参加，尤其是kai
九洲方除百尺冰，映秀又遭蛮牛耕。汽笛嘶鸣国旗半，哀伤尽处是重生。&&&&&-老K
治国就是治吏。礼义廉耻，国之四维。四维不张，国之不国。&&&-毛泽东
等　级：业余侠客
帖　子：357
专家分：201
--------------100
1115524238213673499------------------请问上面算不算一个正确的输入文件,V=100,现在有11件物品,算一下最多能装几件,最大容积是多少?那物品数优先还是容积优先?另:统一下输入文件的名称和V及物品数吧,这们测试的时候方便一些.
其实我也很无聊!
等　级：新手上路
帖　子：625
是体积优先，给个例子，比如输入是10 48 135那么输出应该是9可能方案有2个，8+1和1+3+5比如8+3就不是个合法的方案，因为它超过了背包的最大容积10（8+3=11）
我喜欢创造，一只扑腾着翅膀向天空飞翔的乌鸦
等　级：新手上路
帖　子：87
好难，不会，哈哈。
等　级：业余侠客
帖　子：357
专家分：201
我是刚学C不久,以前用VB,至于C只会简单的程序实现,还不懂得怎样提高程序的通用性,在效率上也差很多.比如N!那题,我是在C++板块见到的,也写了一个,可是没人理会,几位板主的代码我根本看不懂.这个程序我完成了,只是简单的算出了结果,至于其它的我就不会了,包括验证我只会用计算器一下一下的按.代码如下,在WIN-TC下写的:/*////////////////////////////////////////////////////////////*/#include&stdio.h&#include&string.h&int main(){
int v,k,array[1000];
int i,j,max,sum=0,reslen=0,res[500];
FILE *char filename[20];
printf("\nInput filename:");
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
printf("\nCannot open file.\n");
/*读入数据*/
fscanf(fp,"%d%d",&v,&k);
for(i=0;i&k;++i)
fscanf(fp,"%d",&array[i]);
fclose(fp);
/*输出读入的数据*/
printf("v=%d\tk=%d\n\nSorted:",v,k);
/*对K个物品进行排序(选择法)并输出*/
for(i=0;i&k-1;++i)
for(j=i+1;j&k;++j)
if(array[max]&array[j])max=j;
if(max!=i)
array[max]+=array[i];
array[i]=array[max]-array[i];
array[max]=array[max]-array[i];
for(i=0;i&k;++i)
printf("%6d",array[i]);
printf("\n");
/*算法核心代码*/
for(i=0;i&k-1;++i)
if(array[i]&v)
sum=array[i];
for(j=i+1;j&k;++j)
sum+=array[j];
sum-=array[j];
res[reslen]=
/*sum=0;*/
for(i=0;i&++i)
j=j&res[i]?res[i]:j;
printf("\nThe max is:%d",j);
getch();}/*////////////////////////////////////////////////////////*/我用的方法是先将K个物品按体积降序排列,从第一数开始与后面的数相加,超过V就加下一个数,循环一次后将结果存入数组,再从第二个数开始试,直到循环结束.最后从数组中选择最大的数输出.错了别笑我,我可以改的...
[此贴子已经被作者于 20:10:24编辑过]
其实我也很无聊!
等　级：业余侠客
帖　子：357
专家分：201
最大努力了,再不行我就只等看别人的了:#include&stdio.h&#include&string.h&#include&stdlib.h&int main(){
int v,k,array[1000];
int i,j,l,max,sum,result=0;
FILE *char filename[20];
printf("Input filename:");
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
printf("\nCannot open file.\n");
/*读入数据*/
fscanf(fp,"%d%d",&v,&k);
for(i=0;i&k;++i)
fscanf(fp,"%d",&array[i]);
fclose(fp);
/*输出读入的数据*/
printf("v=%d\tk=%d\n\nSorted:",v,k);
/*对K个物品进行排序(选择法)并输出*/
for(i=0;i&k-1;++i)
for(j=i+1;j&k;++j)
if(array[max]&array[j])max=j;
if(max!=i)
array[max]+=array[i];
array[i]=array[max]-array[i];
array[max]=array[max]-array[i];
for(i=0;i&k;++i)
printf("%6d",array[i]);
printf("\n");
/*算法核心代码*/
for(i=0;i&k-1;++i)
if(array[i]&v)
sum=array[i];
for(l=1;l&k-i-2;++l)
printf("%d",array[i]);
for(j=i+l;j&k;++j)
sum+=array[j];printf("+%d",array[j]);
sum-=array[j];printf("-%d",array[j]);
printf("=%d\n",sum);
result=sum&result?sum:
sum=array[i];
printf("\nThe max is:%d",result);}以下是输入:100
12136034470902793578018以下是输出:v=100 k=12
390+80-80+70-70+60-60+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=9990+70-70+60-60+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=9990+60-60+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=9990+44-44+35-35+27-27+18-18+13-13+9+7-7+3-3=9990+35-35+27-27+18-18+13-13+9+7-7+3-3=9990+27-27+18-18+13-13+9+7-7+3-3=9990+18-18+13-13+9+7-7+3-3=9990+13-13+9+7-7+3-3=9990+9+7-7+3-3=9980+70-70+60-60+44-44+35-35+27-27+18+13-13+9-9+7-7+3-3=9880+60-60+44-44+35-35+27-27+18+13-13+9-9+7-7+3-3=9880+44-44+35-35+27-27+18+13-13+9-9+7-7+3-3=9880+35-35+27-27+18+13-13+9-9+7-7+3-3=9880+27-27+18+13-13+9-9+7-7+3-3=9880+18+13-13+9-9+7-7+3-3=9880+13+9-9+7+3-3=10080+9+7+3=9970+60-60+44-44+35-35+27+18-18+13-13+9-9+7-7+3=10070+44-44+35-35+27+18-18+13-13+9-9+7-7+3=10070+35-35+27+18-18+13-13+9-9+7-7+3=10070+27+18-18+13-13+9-9+7-7+3=10070+18+13-13+9+7-7+3=10070+13+9+7+3-3=9970+9+7+3=8960+44-44+35+27-27+18-18+13-13+9-9+7-7+3=9860+35+27-27+18-18+13-13+9-9+7-7+3=9860+27+18-18+13+9-9+7-7+3-3=10060+18+13+9+7-7+3-3=10060+13+9+7+3=9260+9+7+3=7944+35+27-27+18+13-13+9-9+7-7+3=10044+27+18+13-13+9+7-7+3-3=9844+18+13+9+7+3=9444+13+9+7+3=7644+9+7+3=6335+27+18+13+9-9+7+3-3=10035+18+13+9+7+3=8535+13+9+7+3=6735+9+7+3=5427+18+13+9+7+3=7727+13+9+7+3=5927+9+7+3=4618+13+9+7+3=5018+9+7+3=3713+9+7+3=32
The max is:100
[此贴子已经被作者于 20:49:13编辑过]
其实我也很无聊!
等　级：业余侠客
帖　子：357
专家分：201
我也发现了,在遇到下面这组数时得不到正确结果:100 690854331只是我找不到更好的方法了.上面这组数存在"中间跳跃"的问题,改进后能得到正确结果,但修改一下输入仍存在问题,还有"下跳跃"和"多级跳跃"问题存在.用递归的方法会好些,但我不会呀."跳跃"的意思也就是说在我的算法中,当加第N个数没有大于V时只能向下继续加,没有忽略N而从N+1开始(或再向下"跳跃"的问题)的选择,上面的输入就是针对我的算法选的,输出为99,而90+4+3+3或90+5+4+1都是最大值......我的代码再改进也做不到K=50的"多级跳跃"!!我还是再想想吧.....
其实我也很无聊!
等　级：业余侠客
帖　子：357
专家分：201
以下是引用freeforever在 19:51:01的发言：
最大努力了,再不行我就只等看别人的了:
核心算法描述:用的还是穷举的办法,中间加入了一个循环(这样虽多了N次计算,但加入了"跳跃"的方法),并列出最大值的数据相加过程. 再精简的话就是我现在做不到的了......
其实我也很无聊!
版权所有，并保留所有权利。
Powered by , Processed in 0.061537 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved|||||| 更多
比特客户端
我们也在这里：
C语言算法之背包问题
关键字：C语言
　企业软件热点文章
　　在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的为wi ，价值为pi .对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ？i=1pi xi 取得最大值。约束条件为n ？i =1wi xi≤c 和xi？[ 0 ， 1 ] ( 1≤i≤n)。
　　在这个表达式中，需求出xt 的值。xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。 例1-8 在杂货店比赛中你获得了，奖品是一车免费杂货。店中有n 种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi .你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。
　　0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入(假设有足够容量)，然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2， w=[100，10，10]， p =[20，15，15]， c = 1 0 5.当利用价值贪婪准则时，获得的解为x= [ 1 ， 0 ， 0 ]，这种的总价值为2 0.而最优解为[ 0 ， 1 ， 1 ]，其总价值为3 0.
　　另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ，w=[10，20]， p=[5，100]， c= 2 5.当利用重量贪婪策略时，获得的解为x =[1，0]， 比最优解[ 0 ， 1 ]要差。
　　还可以利用另一方案，价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi /wi 值最大的物品，这种策略也不能保证得到最优解。利用此策略试解n= 3 ，w=[20，15，15]， p=[40，25，25]， c=30 时的最优解。
　　我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧， 0 / 1背包问题是一个N P-复杂问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递(增)减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。在6 0 0个随机产生的背包问题中，用这种启发式贪婪算法来解有2 3 9题为最优解。有5 8 3个例子与最优解相差1 0 %，所有6 0 0个答案与最优解之差全在2 5 %以内。该算法能在O (nl o gn)时间内获得如此好的性能。我们也许会问，是否存在一个x (x&1 0 0 )，使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点，考虑例子n =2， w = [ 1 ，y]， p= [ 1 0 ， 9y]， 和c= y.贪婪算法结果为x=[1，0]， 这种方案的值为1 0.对于y≥1 0 / 9，最优解的值为9 y.因此，贪婪算法的值与最优解的差对最优解的比例为( ( 9y - 1 0)/9y* 1 0 0 ) %，对于大的y，这个值趋近于1 0 0 %.但是可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的x% (x&100) 之内。首先将最多k 件物品放入背包，如果这k 件物品重量大于c，则放弃它。否则，剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解。
　　例13-9 考虑n =4， w=[2，4，6，7]， p=[6，10，12，13]， c = 11.当k= 0时，背包按物品价值密度非递减顺序装入，首先将物品1放入背包，然后是物品2，背包剩下的容量为5个单元，剩下的物品没有一个合适的，因此解为x = [ 1 ， 1 ， 0 ， 0 ].此解获得的价值为1 6.
　　现在考虑k = 1时的贪婪启发法。最初的子集为{ 1 } ， { 2 } ， { 3 } ， { 4 }.子集{ 1 } ， { 2 }产生与k= 0时相同的结果，考虑子集{ 3 }，置x3 为1.此时还剩5个单位的容量，按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1，它适合，因此取x1 为1，这时仅剩下3个单位容量了，且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x = [ 1 ， 0 ， 1 ， 0 ]，获得的价值为1 8.若从子集{ 4 }开始，产生的解为x = [ 1 ， 0 ， 0 ， 1 ]，获得的价值为1 9.考虑子集大小为0和1时获得的最优解为[ 1 ， 0 ， 0 ， 1 ].这个解是通过k= 1的贪婪启发式算法得到的。
　　若k= 2，除了考虑k& 2的子集，还必需考虑子集{ 1 ， 2 } ， { 1 ， 3 } ， { 1 ， 4 } ， { 2 ， 3 } ， { 2 ， 4 }和{ 3 ， 4 }.首先从最后一个子集开始，它是不可行的，故将其抛弃，剩下的子集经求解分别得到如下结果：[ 1 ， 1 ， 0 ， 0 ] ， [ 1 ， 0 ， 1 ， 0 ] ， [ 1 ， 0 ， 0 ， 1 ] ， [ 0 ， 1 ， 1 ， 0 ]和[ 0 ， 1 ， 0 ， 1 ]，这些结果中最后一个价值为2 3，它的值比k= 0和k= 1时获得的解要高，这个答案即为启发式方法产生的结果。 这种修改后的贪婪启发方法称为k阶优化方法(k - o p t i m a l)。也就是，若从答案中取出k 件物品，并放入另外k 件，获得的结果不会比原来的好，而且用这种方式获得的值在最优值的( 1 0 0 / (k + 1 ) ) %以内。当k= 1时，保证最终结果在最佳值的5 0 %以内;当k= 2时，则在3 3 . 3 3 %以内等等，这种启发式方法的执行时间随k 的增大而增加，需要测试的子集数目为O (nk )，每一个子集所需时间为O (n)，因此当k &0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。
相关文章：
[ 责任编辑：之极 ] &&&&
软件信息化周刊
比特软件信息化周刊提供以数据库、操作系统和管理软件为重点的全面软件信息化产业热点、应用方案推荐、实用技巧分享等。以最新的软件资讯，最新的软件技巧，最新的软件与服务业内动态来为IT用户找到软捷径。
商务办公周刊
比特商务周刊是一个及行业资讯、深度分析、企业导购等为一体的综合性周刊。其中，与中国计量科学研究院合力打造的比特实验室可以为商业用户提供最权威的采购指南。是企业用户不可缺少的智选周刊！
比特网络周刊向企业网管员以及网络技术和产品使用者提供关于网络产业动态、技术热点、组网、建网、网络管理、网络运维等最新技术和实用技巧，帮助网管答疑解惑，成为网管好帮手。
服务器周刊
比特服务器周刊作为比特网的重点频道之一，主要关注x86服务器，RISC架构服务器以及高性能计算机行业的产品及发展动态。通过最独到的编辑观点和业界动态分析，让您第一时间了解服务器行业的趋势。
比特存储周刊长期以来，为读者提供企业存储领域高质量的原创内容，及时、全面的资讯、技术、方案以及案例文章，力求成为业界领先的存储媒体。比特存储周刊始终致力于用户的企业信息化建设、存储业务、数据保护与容灾构建以及数据管理部署等方面服务。
比特安全周刊通过专业的信息安全内容建设，为企业级用户打造最具商业价值的信息沟通平台，并为安全厂商提供多层面、多维度的媒体宣传手段。与其他同类网站信息安全内容相比，比特安全周刊运作模式更加独立，对信息安全界的动态新闻更新更快。
新闻中心热点推荐
新闻中心以独特视角精选一周内最具影响力的行业重大事件或圈内精彩故事，为企业级用户打造重点突出，可读性强，商业价值高的信息共享平台；同时为互联网、IT业界及通信厂商提供一条精准快捷，渗透力强，覆盖面广的媒体传播途径。
云计算周刊
比特云计算周刊关注云计算产业热点技术应用与趋势发展，全方位报道云计算领域最新动态。为用户与企业架设起沟通交流平台。包括IaaS、PaaS、SaaS各种不同的服务类型以及相关的安全与管理内容介绍。
CIO俱乐部周刊
比特CIO俱乐部周刊以大量高端CIO沙龙或专题研讨会以及对明星CIO的深入采访为依托，汇聚中国500强CIO的集体智慧。旨为中国杰出的CIO提供一个良好的互融互通 、促进交流的平台，并持续提供丰富的资讯和服务，探讨信息化建设，推动中国信息化发展引领CIO未来职业发展。
IT专家新闻邮件长期以来，以定向、分众、整合的商业模式，为企业IT专业人士以及IT系统采购决策者提供高质量的原创内容，包括IT新闻、评论、专家答疑、技巧和白皮书。此外，IT专家网还为读者提供包括咨询、社区、论坛、线下会议、读者沙龙等多种服务。
X周刊是一份IT人的技术娱乐周刊，给用户实时传递I最新T资讯、IT段子、技术技巧、畅销书籍，同时用户还能参与我们推荐的互动游戏，给广大的IT技术人士忙碌工作之余带来轻松休闲一刻。
微信扫一扫
关注Chinabyte}