题目描述
达达帮翰翰给女生送礼物,翰翰一共准备了N个礼物,其中第i个礼物的重量是G[i]。
达达的力气很大,他一次可以搬动重量之和不超过W的任意多个物品。
达达希望一次搬掉尽量重的一些物品,请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
样例
输入样例:
20 5
7
5
4
18
1
输出样例:
19
算法1
(双向dfs) $O(2^{\frac{N}{2}}log 2^{N / 2}) = O(N * 2 ^{N / 2})$
由于题目给的V非常大,如果按照普通背包问题去算的话,时间复杂度$O(NV)$,会爆掉。
而物体的数量N = 46
非常小,所以可以采用爆搜的方法。
但是爆搜$2 ^ {46}$ 也会爆。采用双向dfs, $2 ^ {23}$ 可以过。
第一次搜索,按照从大到小进行搜索,选出若干个0~W重量之间的物品。然后对物品进行排序,去重
第二次搜索,同样也从大到小,如果当前搜索到最后一个数。再对第一次搜索的结果进行二分。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1 << 24;
int n, m, k;
int g[50], weights[N];
int cnt = 0;
int ans;
void dfs(int u, int s){
if (u == k){
weights[cnt ++] = s;
return;
}
if ((LL) s + g[u] <= m) dfs(u + 1, s + g[u]);
dfs(u + 1, s);
}
void dfs2(int u, int s){
if (u == n){
int l = 0, r = cnt - 1;
while (l < r){
int mid = l + r + 1 >> 1;
if (weights[mid] + (LL) s <= m) l = mid;
else r = mid - 1;
}
if (weights[l] + (LL) s <= m) ans = max(ans, weights[l] + s);
return ;
}
if ((LL)s + g[u] <= m) dfs2(u + 1, s + g[u]);
dfs2(u + 1, s);
}
int main(){
cin >> m >> n;
for (int i = 0; i < n; i ++) cin >> g[i];
sort(g, g + n);
reverse(g, g + n);
k = n / 2 + 2;
dfs(0, 0);
sort(weights, weights + cnt);
int t = 1;
for (int i = 1; i < cnt; i ++)
if (weights[i] != weights[i - 1])
weights[t ++] = weights[i];
cnt = t;
dfs2(k, 0);
cout << ans << endl;
return 0;
}