#include"stdio.h"
#include"stdlib.h"
#include"time.h"
clock_t start, finish;
double duration;
int c;
int n;
double w[2000];
double v[2000];
double p[2000];
double cw=0; //背包当前的重量
double cv=0; //背包当前的价值
int bestv=0;
int op[2000];
int lastop[2000];
double temp;
FILE *fp;
int jilu[2000];
double Bound(int i)
{
double cleft=c-cw;
double b=cv;
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=v[i];
i++;
}
//装满背包
if(i<=n)
b+=v[i]*cleft/w[i];
return b;
}
void Backtrack(int i)
{
int j;
if(i>n) //已经到达叶子节点
{
bestv=(int)cv;
for(j=0;j<n;j++)
{
lastop[j]=op[j];
}
return;
}
if(cw+w[i]<=c)
{
op[jilu[i]]=1;
cw+=w[i];
cv+=v[i];
Backtrack(i+1);
op[jilu[i]]=0;
cw-=w[i];
cv-=v[i];
}
if(Bound(i+1)>bestv)
Backtrack(i+1);
}
int main()
{
int i,j,temp1;
w[0]=0;
v[0]=0;
if((fp=fopen("F:\\ca.txt","r"))==0)//文件读入
{
printf("无文件!!\n");
return -1;
}
else
{
fscanf(fp,"%d",&c);
fscanf(fp,"%d",&n);
i=1;
while(i<=n&&!feof(fp))
{
fscanf(fp,"%lf",&w[i]);
fscanf(fp,"%lf",&v[i]);
i++;
}
}
fclose(fp);
for(i=1;i<=n;i++)
{
p[i]=(v[i]/w[i]);
}
for(i=1;i<=n;i++)
jilu[i]=i;
//排序
for(j=1;j<n;j++)
for(i=1;i<=n-j;i++)
if(p[i]<p[i+1])
{
temp=p[i];
p[i]=p[i+1];
p[i+1]=temp;
temp=w[i];
w[i]=w[i+1];
w[i+1]=temp;
temp=v[i];
v[i]=v[i+1];
v[i+1]=temp;
temp1=jilu[i];
jilu[i]=jilu[i+1];
jilu[i+1]=temp1;
}
start = clock();
Backtrack(1);
finish = clock();
printf("%d\n",bestv);
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "%f seconds\n", duration );
for(i=1;i<=n;i++)
{
printf("%d %d\n",i,lastop[i]);
}
return 0;
}
