7
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const ll INF = 0x3f3f3f3f; const int MAX_N = 40 + 2; //输入 int n; ll w[MAX_N], v[MAX_N], W; pair<ll, ll> ps[1 << (MAX_N / 2)]; //重量，价值 void solve(){ int n2 = n / 2; int i, j; for(i = 0;i < 1 << n2;i ++){ //枚举前半部分,i的二进制的每一位算一种情况 ll sw = 0, sv = 0; for(j = 0;j < n2;j ++){ if(i >> j & 1){ //取i的二进制的每一位，1代表取这个数，0代表不取 sw += w[j]; sv += v[j]; } } ps[i] = make_pair(sw, sv); } sort(ps, ps + (1 << n2)); //默认先按first排序，再按second排序 int m = 1; //去除多余元素后的大小 for(i = 1;i < 1 << n2;i ++){ //排序后除去多余的元素 if(ps[m - 1].second < ps[i].second){ ps[m ++] = ps[i]; } } ll res = 0; for(i = 0;i < 1 << (n - n2);i ++){ //折半枚举后半部分 ll sw = 0, sv = 0; for(j = 0;j < n - n2;j ++){ if(i >> j & 1){ sw += w[n2 + j]; sv += v[n2 + j]; } } if(sw <= W){ //此处INF也是long long类型，否则编译会出错 ll tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1)->second; res = max(res, sv + tv); } } printf("%lld\n", res); } int main(){ scanf("%d", &n); for(int i = 0;i < n;i ++){ //输入 scanf("%lld%lld", &w[i], &v[i]); } scanf("%lld", &W); solve(); return 0; }