AcWing 171. 送礼物 - Java
原题链接
简单
作者:
莫里Mori
,
2021-01-27 17:58:55
,
所有人可见
,
阅读 396
/*
1. 对g逆序排序
2. 对[0,n/2+2]个礼物DFS,数组s记录所有可能选取到的重量
3. 对s升序排序,并对[n/2+2,n]个礼物DFS,假设最后取到的重量为x,那么使用二分在s中找到重量y,使得x+y<=w且x+y最大
*/
import java.util.*;
public class Main{
public static Scanner sc = new Scanner(System.in);
public static int n;
public static int w;
public static int[] g = new int[100];
public static int[] s = new int[1 << 24];
public static int ans = 0, count = 0;
public static void dfs1(int i, int t) {
if (i == n / 2 + 2) {
s[count++] = t;
return;
}
if ((long)t + g[i] <= w) {
dfs1(i + 1, t + g[i]);
}
dfs1(i + 1, t);
}
public static void dfs2(int i, int t) {
if (i == n) {
int l = 0;
int r = count - 1;
while (l < r) {
int m = (l + r + 1) / 2;
if ((long)s[m] + t <= w) {
l = m;
} else {
r = m - 1;
}
}
if((long)s[l] + t <= w){
ans = Math.max(ans, s[l] + t);
}
return;
}
if ((long)t + g[i] <= w) {
dfs2(i + 1, t + g[i]);
}
dfs2(i + 1, t);
}
public static void main(String[] args) {
w = sc.nextInt();
n = sc.nextInt();
for (int i = 0; i < n; i++) {
g[i] = sc.nextInt();
}
Arrays.sort(g, 0, n);
for (int i = 0; i < n / 2; i++) {
int tmp = g[i];
g[i] = g[n - i - 1];
g[n - i - 1] = tmp;
}
dfs1(0, 0);
Arrays.sort(s, 0, count);
dfs2(n / 2 + 2, 0);
System.out.println(ans);
}
}