HUGEKNAP - Cái túi ( Hard version )

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10005
#define maxm 1005
double const PI=4*atan(1);

int test,n,m,w[maxn],v[maxn],thutu[maxn],f[maxn][maxm],run,KQ,the,check;

using namespace std;

int main(){
     // freopen("HUGEKNAP.in","r",stdin);
      scanf("%d",&test);
      for(int itest = 1;itest<=test;itest++){
           scanf("%d %d",&n,&m);
           KQ = 0;
           for(int i = 0;i<=m;i++) f[0][i] = 0; 
           for(int i = 1;i<=n;i++)   scanf("%d",&w[i]);
           for(int i = 1;i<=n;i++)   scanf("%d",&v[i]);
           for(int i = 1;i<=n;i++){
                 for(int j = 0;j<=m;j++){
                       f[i][j] = f[i-1][j];
                       if(j>=w[i]) f[i][j] >?= f[i-1][j-w[i]]+v[i];                 
                 }
           }
           for(int i = 0;i<=m;i++){
                   if(KQ < f[n][i]){
                         KQ = f[n][i];
                         check = i;
                   }
           }
           run = 0;
           for(int i = n;i>=1&&check>0;i--){
                 if(f[i][check]!=f[i-1][check]){
                       thutu[run++] = i;
                       check -= w[i];
                 }
           }
           reverse(thutu,thutu+run);
           printf("%d %d\n",KQ,run);
           for(int i = 0;i<run;i++) printf("%d ",thutu[i]);
           printf("\n"); 
      }
     // getch();
}

Download