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

Download