11111111.c

跳棋小游戏

#include<iostream>
using namespace std;
int n; // 物品数量
int c;//背包容量
int *p;//物品价值数组
int *w;//物品重量数组
int *x;//解数组
int *best_x,best_w,best_p;//最优解,最优级重量,最优价值
bool check(int i,int cw);
void tryLoad(int i,int cw,int cp);
void main()
{
 int i;
 cout<<"请你输入物品的数量 n:=";
 cin>>n;
 w=new int[n+1];
 p=new int[n+1];
 x=new int[n+1];
 best_x=new int[n+1];
 best_w=0;
 best_p=0;
 cout<<"请输入背包的总容量 C:=";
 cin>>c;
 cout<<"请你输入各件物品的重量及价值,共"<<n<<"件"<<endl;
 //cout<<"  重量"<<'\t'<<"价值"<<endl;
 for( i=1;i<=n;i++)
 {
  cout<<i<<":=";
  cin>>w[i];
  //cout<<'\t';
     cin>>p[i];
  best_x[i]=x[i]=0;
 }
 cout<<"  重量"<<'\t'<<"价值"<<endl;
 for( i=1;i<=n;i++)
  {
  cout<<i<<":=";
  cout<<w[i]<<'\t'<<p[i]<<endl;
  //best_x[i]=x[i]=0;
 }
 
 tryLoad(1,0,0);
 cout<<endl<<"the best load is:"<<endl;
//fo(i=0;i<
 cout<<"weight:="<<best_w<<endl<<"price:="<<best_p<<endl;
}
bool check(int i,int cw)
{
 if(cw+x[i]*w[i]>c)
  return false;
 else
  return true;
}
void tryLoad(int i,int cw,int cp)
{
 if(i>n)
 {
  cout<<endl;
  for(int k=1;k<=n;k++)
   cout<<" "<<x[k];
  cout<<"cw="<<cw<<'\t'<<"p="<<cp;
  if(cp>best_p)
  {
   best_w=cw;
   best_p=cp;
  }
  for(k=1;k<=n;k++)
   best_x[k]=x[k];
 }
 else
  for(int j=1;j>=0;j--)
  {
   x[i]=j;
   if(check(i,cw))
   {
    cw+=x[i]*w[i];
                cp+=x[i]*p[i];
    tryLoad(i+1,cw,cp);
    cw-=x[i]*w[i];
    cp-=x[i]*p[i];
   }
  }
}