C 背包问题课程设计.doc

//解决“背包问题”的思路及思想如下：

//思想——动态规划法，先考虑没有物品要放的时候S0，
//再考虑只有一个要放物品a的各种情况S1，
//再综合考虑只有第一个a和第二个b物品要放时的情况S2，
//再综合考虑有三个待放物品abc的情况……

#include<stdio.h>
#include<math.h>
#define MAX 200

int 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>.集合中｛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",&M);
printf("\n请输入下列物品初始信息:");
printf("\n物品种类有几种？：");
scanf("%d",&n);

for(num=0;num<n;num++)
{
printf("\n第%d种物品重量：",num+1);
scanf("%d",&wi[num]);
printf("\n 价值：");
scanf("%d",&pi[num]);
}

for(num=0;num<n;num++)
{
temp=wi[0];
q=0;
for(t=0;t<n;t++)
{
if(temp>wi[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<n;i++)
{
F[i+1]=end+1;
u=begin;//从头开始考虑序偶点
for(r=begin;r<end+1;r++)//生成sii图，s1中只考察结点0,
{
if(W[r]+w[i]<=M)
u=(W[r]+w[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;j<u+1;j++)//生成si图
{

ww=W[j]+w[i];
pp=P[j]+p[i];

while(k<=end&&W[k]<ww)//将si-1的点都加到si中
{
P[next]=P[k];
W[next]=W[k];
next++;
k++;
}

if(k<=end&&W[k]==ww)
{
pp=pp>P[k]?pp:P[k];
k++;
}
if(pp>P[next-1])//sii中的点如果效益比以前的大，加进si
{

P[next]=pp;
W[next]=ww;
next++;
}
while(k<=end&&P[k]<=P[next-1])
k++;
}

begin=end+1;
end=next-1;
}

//回溯

PX=P[end];
WX=W[end];
for(i=n;i>0;i--)
{
PY=P[F[i]-1];WY=W[F[i]-1];
if(PX>PY)
{
x[i]=1;
PX=PX-p[i-1];
WX=PY-w[i-1];
}
else x[i]=0;
}
printf("\n最优决策为：");
for(i=0;i<n;i++)
printf("%d",x[s[i]]);
printf("\n最优效益为:%d",P[end]);
printf("\n最优重量为:%d",W[end]);
}