全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
/解决“背包问题”的思路及思想如下:/思想动态规划法,先考虑没有物品要放的时候S0,/再考虑只有一个要放物品a的各种情况S1,/再综合考虑只有第一个a和第二个b物品要放时的情况S2,/再综合考虑有三个待放物品abc的情况#include#include#define MAX 200 int n,M; int num,t,q; int temp; int s100; int x100;/决策集 int ww,pp,i,j,k,r,next; int u;/记录附加结点 int P100000,W100000;/存放所有的可行序偶 /什么叫序偶?答:序偶可以看作两个元素的集合,但序偶具有次序关系 .如 /!=.集合中x,y=y,x int F100;/记录si点的起点在P、W数组中的位置 int begin=0,end=0; int wi100,pi100,w100,p100; int PX,WX,PY,WY;void main(void) printf(n*); printf(n * 背包问题 *); printf(n*); P0=W0=0;/S0中的点(0,0) F0=0; F1=next=1; printf(n请输入下列背包初始信息:); printf(n背包最大容量为:); scanf(%d,&M); printf(n请输入下列物品初始信息:); printf(n物品种类有几种?:); scanf(%d,&n); for(num=0;numn;num+) printf(n第%d种物品重量:,num+1); scanf(%d,&winum); printf(n 价值:); scanf(%d,&pinum); for(num=0;numn;num+) temp=wi0; q=0; for(t=0;twit) temp=wit; q=t; /寻找最小质量的物品,并用q记录其位置 sq=num+1; wnum=wiq; pnum=piq; wiq=MAX; /将物品按其质量的大小,从小到大排序/程序主体“动态规划” for(i=0;in;i+) Fi+1=end+1; u=begin;/从头开始考虑序偶点 for(r=begin;rend+1;r+)/生成sii图,s1中只考察结点0, if(Wr+wi(Wu+wi)?r:u;/s1的u=0,u是sii中能让i结点加上它把空间塞得最满的那个结点,即 /造成s12中x轴最向右靠近确定的M值的点的附加点 /u号以前的点都是可以考虑加入的点 k=begin;/k是记录si-1图中已加入到si图中的点 for(j=begin;ju+1;j+)/生成si图 ww=Wj+wi; pp=Pj+pi; while(k=end&Wkww)/将si-1的点都加到si中 Pnext=Pk; Wnext=Wk; next+; k+; if(kPk?pp:Pk; k+; if(ppPnext-1)/sii中的点如果效益比以前的大,加进si Pnext=pp; Wnext=ww; next+; while(k=end&Pk0;i-) PY=PFi-1;WY=WFi-1; if(PXPY) xi=1; PX=PX-pi-1; WX=PY-wi-1; else xi=0; printf(n最优决策为:); for(i=
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024全案代理销售合同
- 2024仿古茶楼装修排给水管道买卖合同
- 2024包机运输合同范本
- 2024房产抵押贷款合同样本
- 2024广告位租赁合同范本,广告位租赁合同样本
- 2024按揭房转让合同样本
- 江苏省苏州市新区实验中学2022年高三冲刺模拟物理试卷含解析
- 2024买卖合同类纠纷的特点
- 2024国际售货合同 国际贸易合同模板
- 2024劳动合同订立和实施过程中尤其需要诚信
- 精品资料(2021-2022年收藏)煤气柜整体调试方案讲解
- 财务报销登记表
- 词的本义和引申义
- (完整版)商圈调研及数据分析技巧
- 三年级上册数学-乘法巧算ppt课件
- 医院职工内部投诉及建议管理办法
- 桥梁检验批质检表汇总及目录[2020]
- 标签打印机验证方案(共20页)
- 苏教版四年级下册数学期末试卷
- 美术校本课程趣味剪纸活动方案
- 乳酸MSDS产品安全技术说明书
评论
0/150
提交评论