描述

有n个重量和价值分别为 wi 和 vi 的物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值

1 <= n <=40

1 <= wi <= 10^15

1 <= vi <= 10^15

1 <= W <= 10^15

分析：在做的时候毫无头绪，在网上看了其他大神的博客才AC了，数据超大无法使用之前的思路(超时且dp数组开不了这么大)，但是由本题条件可知n的值非常小，可用递归配合剪枝解题

代码：

#include
       
        #include
        
         #include
         
           #define Max(a, b) a > b ? a:busing namespace std;typedef long long ll;const ll INF = 1000000000000000;ll w[45], v[45];ll sw[45], sv[45];ll n, W, ans;void solve(int i, ll W, ll V) {    if(i == 0) {        ans = Max(ans, V);        return;        }    if(W == 0 || ans >= V + sv[i]) return;//背包满或者当前总的加上这个前i个的总价值小于当前的总value，这步是剪枝     if(W >= sw[i]) {
     //因为是从上往下找的，所以只要当前容量能装下前i个的和，所以这时一定是最大的 ,剪枝         V += sv[i];        ans = Max(ans, V);        W = 0;        return;    }    if(w[i] <= W) solve(i-1, W - w[i], V + v[i]);    solve(i-1, W, V);}int main() {    while(cin >> n >> W) {        ans = -1;        memset(sw, 0, sizeof(sw));        memset(sv, 0, sizeof(sv));        for(int i = 1; i <= n; i++) {            cin >> w[i] >> v[i];            sw[i] = sw[i-1] + w[i];            sv[i] = sv[i-1] + v[i];        }        solve(n, W, 0);        cout << ans << endl;    }     return 0;}