• / 4
  • 下载费用:10 金币  

C 背包问题课程设计.doc

关 键 词:
C 背包问题课程设计.doc
资源描述:
//解决“背包问题”的思路及思想如下://思想——动态规划法,先考虑没有物品要放的时候 S0,//再考虑只有一个要放物品 a 的各种情况 S1,//再综合考虑只有第一个 a 和第二个 b 物品要放时的情况 S2,//再综合考虑有三个待放物品 abc 的情况……#include#include#define MAX 200int n,M; int num,t,q;int temp;int s[100];int x[100];//决策集int ww,pp,i,j,k,r,next;int u;//记录附加结点int P[100000],W[100000];//存放所有的可行序偶//什么叫序偶?答:序偶可以看作两个元素的集合,但序偶具有次序关系 .如//!=.集合中{x,y}={y,x}int F[100];//记录 si 点的起点在 P[]、W[]数组中的位置int begin=0,end=0;int wi[100],pi[100],w[100],p[100];int PX,WX,PY,WY;void main(void){printf(“\n******************************************************“);printf(“\n ******************* 背包问题 ***************“);printf(“\n******************************************************“);P[0]=W[0]=0;//S0 中的点(0,0)F[0]=0;F[1]=next=1;printf(“\n 请输入下列背包初始信息:“);printf(“\n 背包最大容量为:“);scanf(“%d“,printf(“\n 请输入下列物品初始信息:“);printf(“\n 物品种类有几种?:“);scanf(“%d“,for(num=0;numwi[t]){temp=wi[t];q=t;} }//寻找最小质量的物品,并用 q 记录其位置s[q]=num+1; w[num]=wi[q]; p[num]=pi[q];wi[q]=MAX; }//将物品按其质量的大小,从小到大排序//程序主体——“动态规划”for(i=0;i(W[u]+w[i])?r:u;//s1 的 u=0,u 是 sii 中能让 i 结点加上它把空间塞得最满的那个结点,即//造成 s12 中 x 轴最向右靠近确定的 M 值的点的附加点}//u 号以前的点都是可以考虑加入的点k=begin;//k 是记录 si-1 图中已加入到 si 图中的点for(j=begin;jP[k]?pp:P[k];k++;}if(ppP[next-1])//sii 中的点如果效益比以前的大,加进 si{P[next]=pp;W[next]=ww;next++;}while(k0;i--){PY=P[F[i]-1];WY=W[F[i]-1];if(PXPY) {x[i]=1;PX=PX-p[i-1];WX=PY-w[i-1];}else x[i]=0;}printf(“\n 最优决策为:“);for(i=0;in;i++)printf(“%d“,x[s[i]]);printf(“\n 最优效益为:%d“,P[end]);printf(“\n 最优重量为:%d“,W[end]); }
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:C 背包问题课程设计.doc
链接地址:https://www.weizhuannet.com/p-7308434.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开