AcWing 171 送礼物

2021-09-26 10:11:56

AcWing 171 送礼物

题目描述

达达帮翰翰给女生送礼物，翰翰一共准备了 N 个礼物，其中第 i 个礼物的重量是 G[i]。
达达的力气很大，他一次可以搬动重量之和不超过 W的任意多个物品。
达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
1 <= N <= 46 , 1 <= W, G[i] <= 2³¹ - 1

输入格式

输出格式

题目分析：

看到这题一开始容易想到背包问题，“力气范围内一次性能搬动的最大重量”，明显是一个01背包问题，然而一看数据，物品个数很少，而背包容量很大，首先开不了背包数组，其次01背包复杂度为O(NV)，即46 * 2³¹，绝对会被T掉。

由于物品个数很少，我们考虑用搜索解决，每个物品有两个状态，一共有2⁴⁶种状态计算，也会TLE。

题目告诉我们最后选择的物品重量不超过W，这是问题的”终态“，在已知初态和终态的情况下，我们可以分别从两边开始搜索（双向搜索），产生两颗深度减半的搜索树，在中间交会、组合成最终的答案。

双向搜索和迭代加深一样，可以避免DFS在深层子树上浪费时间。

先对前半部分搜索，用数组存储所有选择所产生的重量，再对后半部分搜索，每次选择求得一个后半部分产生的总重量ans，我们只需要在前面找出最大但不大于W - ans的重量，在ans确定的情况下，只有这两个相加才可能产生最优解，更新即可。

对存储前半部分重量的数组排序、去重(降低二分复杂度)，即可采用二分法求得ans对应的前半部分的重量。

复杂度分析:

前半部分，只有2^N/2种状态，复杂度为O(2^N/2)，后半部分在前半部分的基础上，对每次的结果还要进行一次二分，因此第二部分为O(2^N/2 * log N/2)，总时间复杂度为O(2^N/2 * log N/2)。

对常数的优化

优化搜索顺序

对于每个物品，在选和不选都有两种状态，但如果选了之后总重量超过了W，那一定不可能成为解，直接剪枝即可。这里如果当前重量越大，越可能发生剪枝从而减少分支结点数量，我们可以对物品按重量从大到小排序。
选取适当的“折半划分点”

我们没有必要一定按对称的数量划分前后部分，事实上，前半部分复杂度比后半部分少了一个log n，我们可以让前半部分多搜索几个物品，以达到在常数上均衡复杂度的效果。

代码如下

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 46;

typedef long long LL;

int w, n, cnt;
int v[N];
LL w1[(1 << 24) + 1], res;

void dfs1 (int cur, LL weight) { // 前1~(n/2)个物品能够凑出来的体积 /  当前的重量
    if (cur == n / 2 + 1) {
        w1[++cnt] = weight;
        return;
    }
    dfs1(cur + 1, weight);
    if (weight + v[cur] <= w) // 剪枝
        dfs1(cur + 1, weight + v[cur]);
}

void dfs2 (int cur, LL weight) {
    if (cur == n + 1) {
        int ans = *lower_bound(w1+1, w1+cnt+1, w - weight, greater<int>());
        // int ans = 0;
        res = max(res, ans + weight);
        return;
    }
    dfs2(cur + 1, weight);
    if (weight + v[cur] <= w) // 剪枝
        dfs2(cur + 1, weight + v[cur]);
}

int main () {
    cin >> w >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    sort(v+1, v+n+1, greater<int>()); // 降序
    dfs1(1, 0);
    sort(w1+1, w1+cnt+1, greater<int>()); // 去重
    cnt = unique(w1+1, w1+cnt+1) - (w1+1); // 返回去重后的数组个数
    dfs2(n / 2 + 1, 0);
    cout << res << endl;
    return 0;
}

AcWing 171 送礼物

码农公寓