#include <iostream>
using std::cin;
using std::cout;
#define MAXN 20
int n,w;
int weight[MAXN],price[MAXN], best[MAXN],now[MAXN];
long int maxprice;
void init() {
int i;
cin >>n >> w;
for(int i=0; i<n;++i) cin >> weight[i];
for(int i=0; i<n;++i) cin >> price[i];
}
void rec(int k, int w, long int st) {
if ( k >= n && st > maxprice){
memcpy (best ,now, sizeof(best));
maxprice=st;
} else if (k<=n) {
for(int i = 0; i < w / weight[k]; ++i ) {
now[k] = i;
rec(k + 1, w - i * weight[k], st + i * price[k]);
}
}
}
int main(){
init();
rec(0, w, 0);
cout <<" " << maxprice << "\n";
return 0;
}
|
