1、/解决“背包问题”的思路及思想如下： /思想 动态规划法，先考虑没有物品要放的时候 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;/存放所有的可行序偶 /什么叫序偶？答：序偶可以看
2、作两个元素的集合 ,但序偶具有次序关系 .如 /!=.集合中 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
3、“, printf(“n 请输入下列物品初始信息 :“); printf(“n 物品种类有几种？： “); scanf(“%d“, for(num=0;numwit) temp=wit; q=t; /寻找最小质量的物品，并用 q 记录其位置 sq=num+1; wnum=wiq; pnum=piq; wiq=MAX; /将物品按其质量的大小，从小到大排序 /程序主体 “动态规划” for(i=0;i(Wu+wi)?r:u;/s1 的 u=0,u 是 sii 中能让 i 结点加上它把空间塞得最满的那个结点，即 /造成 s12中 x轴最向右靠近确定的 M值的点的附加点 /u 号以前的点都是可以考虑
4、加入的点 k=begin;/k 是记录 si-1 图中已加入到 si 图中的点 for(j=begin;jPk?pp:Pk; k+; if(ppPnext-1)/sii 中的点如果效益比以前的大，加进 si Pnext=pp; Wnext=ww; next+; while(k0;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=0;in;i+) printf(“%d“,xsi); printf(“n 最优效益为 :%d“,Pend); printf(“n 最优重量为 :%d“,Wend);
