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();
}