HUGEKNAP - Cái túi ( Hard version )
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 10000
#define WW 1000
int f[N+1][WW+1], n, W, v[N+1], w[N+1], stk[N];
int main() {
int t; scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&W);
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 = w[i]-1; j > 0; --j)
f[i][j] = f[i-1][j];
for(int j = w[i]; j <= W; ++j)
f[i][j] = max(f[i-1][j], v[i]+f[i-1][j-w[i]]);
}
int i = n, j = W, hi = 0;
while(i && j) {
if(f[i][j] == f[i-1][j]) --i;
else {
stk[hi++] = i;
j -= w[i--];
}
}
printf("%d %d\n", f[n][W], hi);
while(hi--) printf("%d ", stk[hi]); printf("\n");
}
return 0;
}