HUGEKNAP - Cái túi ( Hard version )
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#define MAXN 10010
#define MAXM 1010
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
int f[MAXN][MAXM];
int w[MAXN],v[MAXN];
bool u[MAXN];
int n,m;
void init(void) {
scanf("%d",&n);
scanf("%d",&m);
FOR(i,1,n) scanf("%d",&w[i]);
FOR(i,1,n) scanf("%d",&v[i]);
FOR(i,1,n) u[i]=false;
}
void optimize(void) {
REP(i,m+1) f[0][i]=0;
FOR(i,1,n) REP(j,m+1) {
f[i][j]=f[i-1][j];
if (j>=w[i] && f[i][j]<f[i-1][j-w[i]]+v[i]) f[i][j]=f[i-1][j-w[i]]+v[i];
}
}
void trace(void) {
int j=m;
int cu=0;
FORD(i,n,1) {
if (f[i][j]==f[i-1][j]) continue;
u[i]=true;
cu++;
j=j-w[i];
}
printf("%d %d\n",f[n][m],cu);
bool prev=false;
FOR(i,1,n) if (u[i]) {
if (prev) printf(" "); else prev=true;
printf("%d",i);
}
printf("\n");
}
int main(void) {
int t;
scanf("%d",&t);
REP(zz,t) {
init();
optimize();
trace();
}
return 0;
}