#include #include #include struct coin { int n; int * value; double * weight; int * available; // 每種硬幣的個數 int * number; // 現在我選了幾個硬幣 int * maxNumber; // 這個過程中,目前最大的組合 double max; // 最大重量 }; void init (struct coin * x, int n, int *v, double *w, int *a) { int i; x->n = n; x->value = (int *)malloc(sizeof(int) * n); x->weight = (double *)malloc(sizeof(double) * n); x->available = (int *)malloc(sizeof(int) * n); x->number = (int *)malloc(sizeof(int) * n); x->maxNumber = (int *)malloc(sizeof(int) * n); x->max = 0; for(i = 0; i< n ; i++) { x->value[i] = v[i]; x->weight[i] = w[i]; x->available[i] = a[i]; x->number[i] = 0; } } void findSolution( struct coin * x, int target, int from ) { int i; if( x->n <= from ) { if( target == 0 ) { // found a solution // check if this solution has max weight double w = 0; for( i = 0 ; i < x->n ; i++ ) { w += x->weight[i] * x->number[i]; } if( w > x->max ) { x->max = w; for( i = 0 ; i < x->n ; i++ ){ x->maxNumber[i] = x->number[i]; } } } return; } // choose coin from "from" position for( i = 0 ; i <= x->available[from] ; i++ ){ // choose i coin form "from" position x->number[from] = i; findSolution(x, target - x->value[from] * i, from + 1); } } int main() { int num; scanf("%d", &num); double w[num]; // 重量 int v[num]; // 面額 int a[num]; // 數量 int target, i; for(i = 0 ; i < num ; i++) scanf("%d", v+i); for(i = 0 ; i < num ; i++) scanf("%lf", w+i); for(i = 0 ; i < num ; i++) scanf("%d", a+i); struct coin x; scanf("%d", &target); init(&x, num, v, w, a); findSolution(&x, target, 0); printf("%lf\n", x.max); for(i = 0 ; i < num ; i++) printf("%d ", x.maxNumber[i]); printf("\n"); }