DP。
#include <stdio.h>
#include <string.h>
#include <stdlib.h> typedef struct {
int val, vol;
} bone_st; bone_st bones[];
int dp[]; int comp(const void *a, const void *b) {
bone_st *p = (bone_st *)a;
bone_st *q = (bone_st *)b;
if (p->vol == q->vol)
return q->val - p->val;
else
return p->vol - q->vol;
} int main() {
int case_n, n, v;
int i, j, k; scanf("%d", &case_n); while (case_n--) {
scanf("%d %d", &n, &v);
for (i=; i<n; ++i)
scanf("%d", &bones[i].val);
for (i=; i<n; ++i)
scanf("%d", &bones[i].vol); qsort(bones, n, sizeof(bone_st), comp);
memset(dp, , sizeof(dp)); for (i=; i<n; ++i) {
if (bones[i].vol > v)
break;
k = bones[i].val;
for (j=v; j>=bones[i].vol; --j) {
if (k+dp[j-bones[i].vol] > dp[j])
dp[j] = k + dp[j-bones[i].vol];
}
}
printf("%d\n", dp[v]);
} return ;
}