送礼物(双向DFS)

达达帮翰翰给女生送礼物,翰翰一共准备了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)

#include <iostream> #include<algorithm> #include <cstring> using namespace std; const int N = 46; typedef long long LL; int k ,cnt; int w[1 << 25]; int n , m ; int p[N]; int ans; void dfs1(int u ,int s) { if(u == k) { w[cnt++] = s; return ; } dfs1(u+1,s); if((LL)s + p[u] <= m) dfs1(u + 1, s + p[u]); } 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((LL)s + w[mid] <= m)l = mid; else r = mid -1; } ans = max(ans,s + w[l]); return ; } dfs2(u+1,s); if((LL) s + p[u] <= m) dfs2(u +1,s + p[u]); } int main() { cin >> m>>n; for(int i = 0 ; i < n ; i++) cin >> p[i]; k = n /2 + 2; sort(p,p+n); reverse(p,p+n); dfs1(0,0); sort(w,w+cnt); cnt = unique(w,w+cnt)-w; dfs2(k,0); cout << ans ; return 0; }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzddfy.html