whu 1356 Accepted Necklace

//搜索法  通过排序的解法

#include
#include

int sumw[25],sumv[25];
int sw[25],sv[25],x[25];
int n,k,an,max,flag;
int w[25],v[25];

void recur(int p)
{
 for(x[p]=x[p-1]+1;x[p]<=n;x[p]++)
 {
  //用了p-1个  n-(k-p+1)+1
        if(n-x[p]  return;

  if(sumw[p-1]+sw[n-k+p]<=max)  //剩下的最大共k个都比max下就不用算
  {
      if(sumv[p-1]+sv[n-k+p]>an)
    an=sumv[p-1]+sv[n-k+p];
   return;
  }

  if(sumv[p-1]+sv[x[p]]<=an&&(p+n-x[p])==k) //剩下的value和都比an小也不用算
  return;

  sumw[p]=sumw[p-1]+w[x[p]];
  sumv[p]=sumv[p-1]+v[x[p]];
     if(sumw[p]>max) continue;
  if(p  else if(sumv[p]>an)
   an=sumv[p];
 }
}

int main()
{
 int i,j,cas,t1,t2;
 scanf("%d",&cas);
 while(cas--)
 {
     scanf("%d%d",&n,&k);
  for(i=1;i<=n;i++)
  scanf("%d%d",&v[i],&w[i]);
  //qsort(d+1,n,sizeof(d[0]),fun);
  //排序
  for(i=2;i<=n;i++)
  {
   t1=w[i];t2=v[i];
   for(j=i-1;j>=1;j--)
   {
           if(w[j]>t1)
     {w[j+1]=w[j];v[j+1]=v[j];}
     else break;
   }
   w[j+1]=t1;v[j+1]=t2;
  }
  //for(i=1;i<=n;i++)
   //printf("%d %d\n",v[i],w[i]);
  scanf("%d",&max);
  if(w[1]>max)
  {printf("0\n");continue;}
  sw[n]=w[n];sv[n]=v[n];
  for(i=n-1;i>=1;i--)
  {
   sw[i]=sw[i+1]+w[i];
   sv[i]=sv[i+1]+v[i];
  }
  if(sw[1]<=max&&n==k)
  {printf("%d\n",sv[1]);continue;}
  an=0;x[0]=0;sumw[0]=sumv[0]=0;
  flag=1;
  recur(1);
  printf("%d\n",an);
 }
}
/*
100
3 2
1 3
2 2
4 1

*/

 

//以下是没有排序的解法,这样时间更少

#include
#include

int sumw[25],sumv[25];
int sw[25],sv[25],x[25];
int n,k,an,max,flag;
int w[25],v[25];

void recur(int p)
{
 for(x[p]=x[p-1]+1;x[p]<=n;x[p]++)
 {
  //用了p-1个  n-(k-p+1)+1
        if(n-x[p]  return;

  if(sumw[p-1]+sw[x[p]]<=max&&((n-x[p]+p)==k))  

  {//剩下的最大共k个都比max下就不用算

   //这里没有排序所以不能说明最后的最大,而要通过判断是不是k个来计算
      if(sumv[p-1]+sv[x[p]]>an)
    an=sumv[p-1]+sv[x[p]];
   return;
  }

  if(sumv[p-1]+sv[x[p]]<=an&&(p+n-x[p])==k) //剩下的value和都比an小也不用算
  return;

  sumw[p]=sumw[p-1]+w[x[p]];
  sumv[p]=sumv[p-1]+v[x[p]];
     if(sumw[p]>max) continue;
  if(p  else if(sumv[p]>an)
   an=sumv[p];
 }
}

int main()
{
 int i,j,cas,t1,t2;
 scanf("%d",&cas);
 while(cas--)
 {
     scanf("%d%d",&n,&k);
  for(i=1;i<=n;i++)
  scanf("%d%d",&v[i],&w[i]);
  /*
  //qsort(d+1,n,sizeof(d[0]),fun);
  //排序
  for(i=2;i<=n;i++)
  {
   t1=w[i];t2=v[i];
   for(j=i-1;j>=1;j--)
   {
           if(w[j]>t1)
     {w[j+1]=w[j];v[j+1]=v[j];}
     else break;
   }
   w[j+1]=t1;v[j+1]=t2;
  }
  */
  //for(i=1;i<=n;i++)
   //printf("%d %d\n",v[i],w[i]);
  scanf("%d",&max);
  if(w[1]>max)
  {printf("0\n");continue;}
  sw[n]=w[n];sv[n]=v[n];
  for(i=n-1;i>=1;i--)
  {
   sw[i]=sw[i+1]+w[i];
   sv[i]=sv[i+1]+v[i];
  }
  if(sw[1]<=max&&n==k)
  {printf("%d\n",sv[1]);continue;}
  an=0;x[0]=0;sumw[0]=sumv[0]=0;
  flag=1;
  recur(1);
  printf("%d\n",an);
 }
}
/*
100
3 2
1 3
2 2
4 1

*/

//////变化了某些限制顺序  0ms过的

#include
#include

int sumw[25],sumv[25];
int sw[25],sv[25],x[25];
int n,k,an,max,flag;
int w[25],v[25];

void recur(int p)
{
 for(x[p]=x[p-1]+1;x[p]<=n;x[p]++)
 {
/*
  //用了p-1个  n-(k-p+1)+1
        if(n-x[p]  return;
*/
  if(sumv[p-1]+sv[x[p]]<=an) //剩下的value和都比an小也不用算 &&(p+n-x[p])==k(可以不要)
  return;

  if(((n-x[p]+p)==k)&&sumw[p-1]+sw[x[p]]<=max)  //剩下的最大共k个都比max下就不用算
  {
      if(sumv[p-1]+sv[x[p]]>an)
    an=sumv[p-1]+sv[x[p]];
   return;
  }
  sumw[p]=sumw[p-1]+w[x[p]];
     if(sumw[p]>max) continue;
  sumv[p]=sumv[p-1]+v[x[p]];  ///////////////调到了continue下面
  if(p  else if(sumv[p]>an)
   an=sumv[p];
 }
}

int main()
{
 int i,j,cas,t1,t2;
 scanf("%d",&cas);
 while(cas--)
 {
     scanf("%d%d",&n,&k);
  for(i=1;i<=n;i++)
  scanf("%d%d",&v[i],&w[i]);
  scanf("%d",&max);
  sw[n]=w[n];sv[n]=v[n];
  for(i=n-1;i>=1;i--)
  {
   sw[i]=sw[i+1]+w[i];
   sv[i]=sv[i+1]+v[i];
  }
  if(sw[1]<=max&&n==k)
  {printf("%d\n",sv[1]);continue;}
  if(sw[1]>max&&n==k)
     {printf("0\n");continue;}
  an=0;x[0]=0;sumw[0]=sumv[0]=0;
  flag=1;
  recur(1);
  printf("%d\n",an);
 }
}
/*
100
3 2
1 3
2 2
4 1

*/