AcWing 171. 送礼物

题目传送门

一、题目解析

二、实现代码

#include 

using namespace std;
const int N = 48; // 1≤N≤46
typedef long long LL;

int n;               // N个礼物
int m;               // 重量之和不超过m,上限,这是一个整数
int k;               // 前k个，即索引下标0~k-1,最大值为N/2，就当25算
int w[N];            // 每个礼物的重量
int sum[1 << N / 2]; //前半段组合可能出现的所有和
//前半部分收集到的所有和,下标因为一直在保持++状态，所以最后一次执行完，也可以理解为前半部分数组的个数
//在排序去重后，此变更也可以视为前半段数组的元素个数，在二分中，因为需要使用的是索引号：0~cnt-1
int cnt;
int ans; //最大重量

// u:第几号礼物，下标从0开始
// s:本路线上累加的礼物物理和
void dfs1(int u, int s) {
    if (u == k) {       //如果能够到达第k个下标位置，表示前面0~k-1共k个选择完毕
        sum[cnt++] = s; //记录礼物重量和
        return;
    }

    //放弃u号物品,走到下一个u+1号面前
    dfs1(u + 1, s);

    //如果加上u号物品重量，不会超过上限m，那么可以选择
    if ((LL)s + w[u] <= m) dfs1(u + 1, s + w[u]);
}

//后半部分
void dfs2(int u, int s) {
    if (u == n) {
        int l = 0, r = cnt - 1;
        //利用二分模板2，找出<=m的右边界
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if ((LL)sum[mid] + s <= m)
                l = mid;
            else
                r = mid - 1;
        }
        //更新更大的重量
        ans = max(ans, sum[l] + s);
        return;
    }
    //放弃当前礼物
    dfs2(u + 1, s);
    //如果加上u号物品重量，不会超过上限m，那么可以选择
    if ((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]);
}
int main() {
    //先读入m再读入n,别整反了
    cin >> m >> n;
    for (int i = 0; i < n; i++) cin >> w[i]; //每个礼物重量
    //由大到小排序
    sort(w, w + n, greater());

    //一家一半
    k = n / 2;

    //前面开始搜索 0~k-1
    // dfs1，枚举出了所有可能出现的组合值
    dfs1(0, 0);

    //结果排序
    sort(sum, sum + cnt);

    //去重
    cnt = unique(sum, sum + cnt) - sum; //最后这个-1是换算出sum数据最后一个的下标

    //后半部分搜索 k~n
    dfs2(k, 0);

    //输出答案
    cout << ans << endl;
    return 0;
}