牛牛的背包问题

题目难度：三星
考察点：二进制枚举、中途相遇法

方法1：暴力二进制枚举

1. 分析：
   每个零食有放和不放两种情况，那么对于n个零食来说就有2^n种情况，我们对于这2^n种情况挨个判断每种情况的体积数是否超过背包容量w，如果没有超过背包容量就记录答案。
   Tips：注意结果用long long

算法实现：
(0). 首先计算全部的状态all=(1<<n)。
(1). 遍历这all种状态
(2). 对于每种状态计算当前的体积值，如果体积值<=w，记录结果ans++
(3). 输出结果

2. 复杂度分析：
   时间复杂度：O(n*2^n)
   空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   const int MAXN = 35;
   int a[MAXN];
   int main() {
    int n, w; cin>>n>>w;
    for(int i=0; i<n; i++) cin>>a[i];
    int ans = 0;
    for(int i=0; i<(1<<n); i++) {
        LL sum = 0;
        for(int j=0; j<n; j++) {
            if(i&(1<<j)) sum += a[j];
        }
        if(sum <= w) ans++;
    }
    cout<<ans<<endl;
    return 0;
   }

方法1：二进制枚举、二分、中途相遇法

1. 分析：
   由于直接进行二进制枚举的算法时间复杂度太高显然是不可行的，那么我们可以借助中途相遇法的思想，将n个零食分为两部分[1, n/2]，(n/2, n]，然后枚举前一部分的所有可能取法，将这些可能取法用一个vector数组记录下来，然后枚举剩余的后一部分的所有可能取法，对于后一部分的可能取法获得其体积值，然后用tmp=背包容量值-当前体积值，我们只需要在前一部分的所有可能取法数组种找到第一个>tmp的下标，此时就知道在前一部分有多少个是满足条件的，将下标即个数记录到结果中。
   Tips：注意结果用long long

算法实现：
(0). 将n件物品分为两部分，用数组v保存前一部分所有可能取法的体积值
(1). 遍历剩余的后一部分的可能取法
(2). 对于每种状态计算背包容量与当前体积值的差值tmp，然后在数组v中二分查找第一个大于tmp的值的下标，此时下标就是在前一部分中有多少种状态与当前体积相加之和满足不超过背包容量的个数。
(3). 输出最终结果

2. 复杂度分析：
   时间复杂度：
   空间复杂度：O()

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   const int MAXN = 35;
   int a[MAXN];
   int main() {
    int n, w; cin>>n>>w;
    for(int i=0; i<n; i++) cin>>a[i];
    int half = n / 2;
    vector<LL> v;
    for(int i=0; i<(1<<half); i++) {
        LL sum = 0;
        for(int j=0; j<half; j++) {
            if(i&(1<<j)) sum += a[j];
        }
        v.push_back(sum);
    }
    sort(v.begin(), v.end());
    LL ans = 0;
    half = n-n/2;
    for(int i=0; i<(1<<half); i++) {
        LL sum = 0;
        for(int j=0; j<half; j++) {
            if(i&(1<<j)) sum += a[j+n/2];
        }
        if(w-sum >= 0) ans += upper_bound(v.begin(), v.end(), w-sum)-v.begin();
    }
    cout<<ans<<endl;
    return 0;
   }