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

Download