1755. 最接近目标值的子序列和
给你一个整数数组 nums 和一个目标值 goal 。
你需要从 nums 中选出一个子序列,使子序列元素总和最接近 goal 。也就是说,如果子序列元素和为 sum ,你需要 最小化绝对差 abs(sum - goal) 。
返回 abs(sum - goal) 可能的 最小值 。
注意,数组的子序列是通过移除原始数组中的某些元素(可能全部或无)而形成的数组。
提示:
1 <= nums.length <= 40
-107 <= nums[i] <= 107
-109 <= goal <= 109
经典双端dfs题。
纯dfs爆搜,时间复杂度2^40,直接起飞:
class Solution {
int res = Integer.MAX_VALUE, goal;
public int minAbsDifference(int[] nums, int _goal) {
goal = _goal;
dfs(nums,0,0);
return res;
}
void dfs(int[] nums,int u, int s) {
if(u == nums.length) {
res = Math.min(res, Math.abs(s-goal));
return;
}
dfs(nums, u+1, s);
dfs(nums, u+1, s + nums[u]);
}
}
双端dfs,空间换时间。将数组分为左右两部分,左边dfs并把所有可能结果开数组排序存起来;右边dfs,对于右边每个结果去和左边的结果相加,找到一个和左边结果相加<=goal的最大值的左边结果,使得相加结果>=goal的最小值的左边结果就在刚刚找到的左边结果+1的位置。由于左边是排序的因此时间复杂度2^20 * 20 * 2。第一个2^20 * 20 用于左半边排序,第二个2^20 * 20 用于右半边dfs和左半边二分。
class Solution {
int res = Integer.MAX_VALUE, cnt = 0, n, goal;
int[] q;
public int minAbsDifference(int[] nums, int _goal) {
n = nums.length;
q = new int[(int)Math.pow(2, n / 2 + 1)];
goal = _goal;
dfs1(nums,0,0);
Arrays.sort(q,0,cnt);
dfs2(nums, (n + 1) / 2, 0);
return res;
}
void dfs1(int[] nums, int u, int s) {
if(u == (n + 1) / 2) {
q[cnt++] = s;
return;
}
dfs1(nums, u+1, s);
dfs1(nums, u+1, s + nums[u]);
}
void dfs2(int[] nums, int u, int s) {
if(u == n) {
int l = 0, r = cnt - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(q[mid] + s <= goal) l = mid;
else r = mid - 1;
}
res = Math.min(res,Math.abs(q[r] + s - goal));
if(r + 1< cnt) res = Math.min(res,Math.abs(q[r + 1] + s - goal));
return;
}
dfs2(nums, u+1, s);
dfs2(nums, u+1, s + nums[u]);
}
}
Ac171. 送礼物
达达帮翰翰给女生送礼物,翰翰一共准备了N个礼物,其中第i个礼物的重量是G[i]。
达达的力气很大,他一次可以搬动重量之和不超过W的任意多个物品。
达达希望一次搬掉尽量重的一些物品,请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
数据范围
1≤N≤46,
1≤W,G[i]≤2^31−1
其实就是1755. 最接近目标值的子序列和一类题,通过双向dfs空间换时间。
注意溢出问题。
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static int w, n, res = 0, cnt = 0;
static int[] g;
static long[] q;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
w = sc.nextInt();
n = sc.nextInt();
g = new int[n];
q = new long[(int)Math.pow(2, n / 2 + 1)];
for(int i = 0; i < n; i++) g[i] = sc.nextInt();
dfs1(0, 0);
Arrays.sort(q, 0, cnt);
dfs2(n / 2, 0);
System.out.println(res);
}
static void dfs1(int u, long s) {
if(u == n / 2) {
q[cnt++] = s;
return;
}
dfs1(u + 1, s);
dfs1(u + 1, s + g[u]);
}
static void dfs2(int u, long s) {
if(u == n) {
int l = 0, r = cnt - 1;
while( l < r) {
int mid = l + r + 1 >> 1;
if(q[mid] + s <= w) l = mid;
else r = mid - 1;
}
if(q[l] + s <= w) res = Math.max(res, (int)(q[l] + s));
return;
}
dfs2(u + 1, s);
dfs2(u + 1, s + g[u]);
}
}