#include "stdafx.h"
#include"iostream"
using namespace std;
const int Arsize=50;
class Knap
{
public:
friend int Knapsack(int p[],int w[],int c,int n);
void print()
{
for (int k=0;k<n;k++)
cout<<bestx[k]<<" ";
cout<<endl;
}
private:
int Bound(int i);
void Backtrack(int t);
int c;
int n;
int *w;
int *p;
int cw;
int cp;
int bestp;
int *bestx;
int *x;
};
int Knap::Bound(int i)
{
int cleft=c-cw;
int b=cp;
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];i++;}
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int t)
{
if(t>n)
{
for (int j=0;j<n;j++)
bestx[j]=x[j];
bestp=cp;
return;
}
if(cw+w[t]<=c)
{
x[t]=1;
cw+=w[t];
cp+=p[t];
Backtrack(t+1);
cw-=w[t];
cp-=p[t];
}
if(Bound(t+1)>bestp)
{
x[t]=0;Backtrack(t+1);
}
}
class Object
{
public:
friend void Sort(Object *Q,int n);
friend int Knapsack(int p[],int w[],int c,int n);
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int id;
float d;
};
void Sort(Object *Q,int n)
{
for (int j=0;j<n;j++)
for (int i=0;i<n-1-j;i++)
if(Q[i].d<Q[i+1].d)
{
int t=Q[i].d;
Q[i].d=Q[i+1].d;
Q[i+1].d=t;
}
}
int Knapsack(int p[],int w[],int c,int n)
{
int W=0;int P=0;int i=1;
Object *Q=new Object[n];
for (i=0;i<n;i++)
{
Q[i].id=i;
Q[i].d=1.0*p[i]/w[i];
P+=p[i];W+=w[i];
}
if(W<=c) return P;
Sort(Q,n);
Knap K;
K.p=new int[n+1];
K.w=new int[n+1];
K.x=new int[n+1];
K.bestx=new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for (i=0;i<n;i++)
{
K.p[i]=p[Q[i].id];
K.w[i]=w[Q[i].id];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
K.Backtrack(1);
K.print();
delete[]Q;delete[]K.w;delete[]K.p;
return K.bestp;
}
int _tmain(int argc, _TCHAR* argv[])
{
int p[Arsize];int w[Arsize];int c,n,best;
cout<<"请输入背包容量：";
cin>>c;
cout<<"请输入物品种类的数量:";
cin>>n;
for (int i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"种物品的重量和价值（用空格隔开）：";
cin>>w[i]>>p[i];
}
cout<<"提示：输出0不拿，1为拿."<<endl;
best=Knapsack(p,w,c,n);
cout<<"最优解为："<<best<<endl;
return 0;
}