/*n和limit分别为物品件数和背包容量,成员sw,sp分别存储装入背包的物品总重量和总价值,成员bound存储目标函数值,
结构体类型 struct pttype数组变量PT[n]存储待处理结点表(即表PT),
变量limit存储背包的容量,变量down、up分别存储目标函数的上下界,变量r记录表PT中的元素个数*/
#include<stdio.h>
#define n 5
#define limit 10
struct Pttype /*表PT中的元素类型*/
{
int t;
int x[n];
int sw,sp,bound;
}
main()
{
int w[n]={2,2,3,5,5},p[n]={10,8,9,10,5};
struct Pttype PT[10];
struct Pttype x,y;
int j,k;
int down=27,up=50;
int r=-1;
x.t=0;
x.sw=0;
x.sp=0;
while(x.t<n)
{/*对结点x进行扩展表*/
for(j=1;j>=0;j--)
{
y=x;y.x[y.t]=j;
y.sw=y.sw+j*w[y.t];
y.sp=y.sp+j*p[y.t];
y.t=y.t+1;
y.bound=y.sp+(limit-y.sw)*(p[y.t]/w[y.t]);
if(y.sw<=limit&&y.bound>=down)
{
k=r;
while(k>=0 &&y.bound>PT[k].bound)
{PT[k+1]=PT[k];k=k-1;}
PT[k+1]=y;
r=r+1;
}
}
/*取下一个扩展结点*/
x=PT[0];
for(k=1;k<=r;k++)
PT[k-1]=PT[k];
r=r-1;
}
/*输出结果*/
printf("0-1背包问题(装入背包的物品重量和价值以表格形式数尺如下:)\n");
printf("j w[j] p[j]\n");
for(j=0;j<n;j++)
if(x.x[j]==1)
printf("%5d %8d %8d \n",j,w[j],p[j]);
printf("装入背包的总重量为:%6d;总价值为:%6d.\n",x.sw,x.bound);
}