建设免费网站模板,wordpress如何不显示评论,wordpress 后台 修改,wordpress代码按钮题目描述
达达帮翰翰给女生送礼物#xff0c;翰翰一共准备了NNN 个礼物#xff0c;其中第 iii 个礼物的重量是 G[i]G[i]G[i]。
达达的力气很大#xff0c;他一次可以搬动重量之和不超过 WWW 的任意多个物品。
达达希望一次搬掉尽量重的一些物品#xff0c;请你告诉达达在…题目描述
达达帮翰翰给女生送礼物翰翰一共准备了NNN 个礼物其中第 iii 个礼物的重量是 G[i]G[i]G[i]。
达达的力气很大他一次可以搬动重量之和不超过 WWW 的任意多个物品。
达达希望一次搬掉尽量重的一些物品请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数分别代表 WWW 和 NNN。
以后 N 行每行一个正整数表示 G[i]G[i]G[i]。
输出格式
仅一个整数表示达达在他的力气范围内一次性能搬动的最大重量。
数据范围
1≤N≤461 \le N \le 461≤N≤46 1≤W,G[i]≤231−11 \le W,G[i] \le 2 ^ {31} - 11≤W,G[i]≤231−1
输入样例
20 5
7
5
4
18
1输出样例
19思路
由于取得方法有2462^{46}24670368744177664种肯定超时。但如果将其分成两组每组就只有2232^{23}2238388608种这就可以过了。先将第一组可能组成的数存入数组要去重不然TLE然后再枚举第二组枚举到一个数就二分搜索与第一组可以组成最大的数。
代码
#include iostream
#include algorithm
using namespace std;int n, w, k;
int a[50];
int pp[16777216], p[16777216], cnt, cnt1, ans;bool cmp(int x, int y)
{return x y;
}void dfs1(int step, int last)
{if (step n / 2) {pp[cnt] last;return;}if ((long) last a[step] w) dfs1(step 1, last a[step]);dfs1(step 1, last);
}void dfs2 (int step, int last)
{if (step n) {int l 0, r cnt - 1;while(l r) {int mid (l r 1) / 2;if ((long) p[mid] last w) l mid;else r mid - 1;}if ((long) p[l] last w) ans max(ans, p[l] last);return;}if ((long) last a[step] w) dfs2(step 1, last a[step]);dfs2(step 1, last);
}int main() {cin w n;for (int i 0; i n; i) cin a[i];sort(a, a n, cmp);k n / 2;dfs1(0, 0);sort(pp, pp cnt);int cnt1 cnt;cnt 0;for (int i 1; i cnt1; i){if (pp[i] ! pp[i - 1]) p[cnt] pp[i];}dfs2(n / 2, 0);cout ans endl;return 0;
}
