题目描述
达达帮翰翰给女生送礼物,翰翰一共准备了N个礼物,其中第i个礼物的重量是G[i]。
达达的力气很大,他一次可以搬动重量之和不超过W的任意多个物品。
达达希望一次搬掉尽量重的一些物品,请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数,分别代表W和N。
以后N行,每行一个正整数表示G[i]。
输出格式
仅一个整数,表示达达在他的力气范围内一次性能搬动的最大重量。
数据范围
1≤N≤46,
1≤W,G[i]≤231−1
样例
输入样例:
20 5
7
5
4
18
1
输出样例:
19
双向DFS
思路
乍一眼过去这道题像背包问题,但是由于每个物品价值太大了,所以背包的O(n^2)的做法肯定会超时
如果暴力枚举每个物品选或不选的组合数法,复杂度将会达到2^46
剪枝方面只能优化搜索顺序.所以此时想到双向DFS,先对前面的物品使用DFS打表,再对后面的物品DFS计算每个方案得价值,再到表里去搜索
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=50;
int n,v;
int w[N];
long long pre[1<<25];
int cnt;
long long res;
void dfs1(int u,long long sum)
{
if(sum>v)return;
if(u>n/2+1)
{
pre[cnt++]=sum;
return;
}
dfs1(u+1,sum);
dfs1(u+1,sum+w[u]);
}
void dfs(int u,long long sum)
{
if(sum>v)return;
if(u>=n)
{
int l=0,r=cnt-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if (sum + pre[mid] <= v) l = mid;
else r = mid - 1;
}
res=max(res,sum+pre[l]);
return;
}
dfs(u+1,sum);
dfs(u+1,sum+w[u]);
}
int main()
{
cin>>v>>n;
for(int i=0;i<n;i++) cin>>w[i];
sort(w, w + n);
reverse(w, w + n);
dfs1(0,0);
sort(pre,pre+cnt);
dfs(n/2+2,0);
cout<<res;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
我是傻逼