494. Target Sum
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
- For example, if
nums = [2, 1], you can add a'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Constraints:
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
Solution:
假设所有数的和为\(s\), 添加正数的和\(p\), 那么负数的和为\(-(s-p)\), 那么\(p - (s- p) = t\). 把该式子化简下, 可得\(2p-s=t\), 即\(p =(s+t)/2\)
因为可以被除以2, 所以p一定是个偶数, 且p因为是正数, 所以s+t也一定是正数
运筹学:
01 背包问题 是一个经典的组合优化问题，其核心是如何在资源有限的情况下选择最优的方案以最大化收益
问题描述:
你有一个固定容量的背包，和 nnn 件物品，每件物品都有：
- 重量 \(w[i]\)
- 价值 \(v[i]\)
目标是： 在不超过背包容量\(W\)的前提下，选择若干物品放入背包，使得背包中物品的总价值最大化.
决策变量:
-
定义\(x[i] \in {0, 1}\) , 表示是否选择物品\(i\):
-
\(x[i]=1\): 表示选择物品\(i\)
- \(x[i] = 0\): 表示不选择物品\(i\)
设\(x[i]\)表示是否选择物品\(i\), 其中: $$ x[i] \in {0,1}, i=1,2,\cdots,n $$
目标函数: $$ Z = \max\sum_{i = 1}^{n}v[i]\cdot x[i] $$ 约束条件: $$ \sum_{i = 1}^{n}w[i]\cdot x[i] \leq W $$ 动态规划
状态定义:
令\(dp[j]\) 表示在容量\(j\)的背包下能获得的最大值
状态转移方程: $$ dp[j] = max(dp[j], dp[j - w[i]] + v[i]) $$ 这里的\(dp[j -w[i]] + v[i]\) 表示选择当前物品\(i\) 后的价值, 取两者中的最大值
边界条件: $$ dp[0]=0 $$
public class knapsack{
public static int knapsack(int[] weights, int values, int W){
int n = weights.length;
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++){
for (int j = W; j >= weights[i]; j--){
dp[j] = math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
public static void main(String[] args) {
// 测试用例
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 8};
int W = 8;
int maxValue = knapsack(weights, values, W);
System.out.println("最大价值: " + maxValue); // 输出: 最大价值: 11
}
}
// TC: O(n x W), 其中$n$是物品数量, W是背包容量.
// SC: O(W)
0-1 Knapsack
0-1 背包: 有\(n\) 个物品, 第\(i\) 个物品的体积为\(w[i]\), 价值为\(v[i]\), 每个物品至多选一个, 求体积和不超过capacity时的最大价值和
回溯三问:
- 当前操作? 枚举第\(i\) 个物品选或不选:
不选, 剩余容量不变; 选, 剩余容量减少\(w[i]\)
-
子问题? 在剩余容量为c时, 从前\(i\) 个物品中得到的最大价值和
-
下一个子问题? 分类讨论:
不选: 在剩余容量为\(c\) 时, 从前\(i - 1\) 个物品中得到的最大价值和
选: 在剩余容量为\(c - w[i]\) 时, 从前\(i - 1\)个物品中得到的最大价值和
public class knapsack{
public static int knapsack(int[] weights, int[] values, int c){
int n = weights.length;
return dfs(n - 1, weights, values, c);
}
private static int dfs(int i, int[] weights, int[] values, int c){
if (i < 0){
return 0;
}
if (weights[i] > c){
// 体积超过当前容量了 -> 不选
return dfs(i - 1, weights, c);
}
// 选
return Math.max(dfs(i - 1, weights, c), dfs(i - 1, weights, c - weights[i]) + values[i]);
}
public static void main(String[] args) {
// 测试用例
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 8};
int W = 8;
int maxValue = knapsack(weights, values, W);
System.out.println("最大价值: " + maxValue); // 输出: 最大价值: 11
}
}
// TC: O(n x c), 其中c是物品数量, c是背包容量.
// SC: O(c)
Backtrack
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// s+ t
int sum = 0;
for (int i = 0; i < nums.length; i++){
sum = sum + nums[i];
}
// s+ t
target = target + sum;
if (target < 0 || target % 2 != 0){
return 0;
}
// p = (s +t)/2
target = target/2;
int n = nums.length;
return dfs(n - 1, nums, target);
}
private int dfs(int i, int[] nums, int target){
if (i < 0){
if (target == 0){
return 1;
}else{
return 0;
}
}
if (nums[i] > target){
return dfs(i - 1, nums, target);
}
return dfs(i - 1, nums, target) + dfs(i - 1 , nums, target - nums[i]);
}
}
class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
int index = 0;
int sum = 0;
dfs(nums, index, sum, target);
return count;
}
private void dfs(int[] nums, int index, int sum, int target){
if (index == nums.length){
if (sum == target){
count++;
}
return;
}
dfs(nums, index + 1, sum + nums[index], target);
dfs(nums, index + 1, sum - nums[index], target);
}
}
// TC: O(branch^level) = O(2^n)
// SC: O(n)
/*
1 1 1 1 1
index i 1
+/ \-
1+1 1-1
/\
index
index: means current nums[index]
*/
class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
int index = nums.length - 1;
int sum = 0;
for (int i = 0; i < nums.length; i++){
sum = sum + nums[i];
}
target = sum + target;
if (target < 0 || target % 2 != 0){
return 0;
}
target = target /2;
int result = dfs(nums, index, target);
return result;
}
private int dfs(int[] nums, int index, int target){
if (index < 0){
if (target == 0){
return 1;
}
return 0;
}
if (target < nums[index]){ // 超过背包容量了
return dfs(nums, index - 1, target);
}
return dfs(nums, index - 1, target) + dfs(nums, index - 1, target - nums[index]);
}
}
递归搜索 + 保存计算结果 = 记忆化搜索
设 \(nums\) 的元素和为 \(s\)，其中添加正号的元素之和为 \(p\)，其余添加负号的元素（绝对值）之和为 \(q\)，那么有 $$ p+q=s $$
Input: nums = [1,1,1,1,1], target = 3 Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3 s = 1 + 1 + 1 + 1 + 1 = 5 -1 + 1 + 1 + 1 + 1 = 3 |-1| + |1 + 1 + 1 + 1| = 5 q + p = 5 1 + 4 = 5 p - q = target 4 - 1 = 3
又因为表达式运算结果等于 \(target\)，所以有 $$ p−q=target $$ 解得 $$ \begin{cases} & p = \frac{s + target}{2}\ & q = \frac{s - target}{2} \end{cases} $$ 这意味着，只要我们选出的取正号的元素和恰好等于\(p\)，或者取负号的元素和恰好等于\(q\)，就等价于表达式的结果恰好等于 \(target\). 所以问题变成从 nums 中选一些数，使得这些数的元素和恰好等于 \(p\)（或者 \(q\)）的方案数.
- 如果 \(target \geq 0\)，那么取 \(q=\frac{s−target}{2}\) 作为背包容量比 \(p\) 更好.
- 如果\(target < 0\), 那么取\(p = \frac{s + target}{2}\)作为背包容量比\(q\) 更好.
综上所述, 取 $$ \frac{s - |target|}{2} $$ 作为0-1背包的背包容量是最优的. (注意target 可以是负数)
如果 \(s−|target|\) 是奇数，那么\(\frac{s - target}{2}\) 是小数. 由于无法从整数中选出一些数，元素和等于小数，所以当 \(s -|target|\) 是奇数的时候，方案数是 \(0\)，直接返回\(0\)就行.
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// s+ t
int sum = 0;
for (int i = 0; i < nums.length; i++){
sum = sum + nums[i];
}
// s+ t
target = target + sum;
if (target < 0 || target % 2 != 0){
return 0;
}
// p = (s +t)/2
target = target/2;
int n = nums.length;
int[][] memo = new int[n][target + 1];
for (int[] row : memo){
Arrays.fill(row, -1);
}
return dfs(n - 1, nums, target, memo);
}
private int dfs(int i, int[] nums, int target, int[][] memo){
if (i < 0){
if (target == 0){
return 1;
}else{
return 0;
}
}
if (memo[i][target] != -1){
return memo[i][target];
}
if (nums[i] > target){
memo[i][target] = dfs(i - 1, nums, target, memo);
return memo[i][target];
}
memo[i][target] = dfs(i - 1, nums, target, memo) + dfs(i - 1 , nums, target - nums[i], memo);
return memo[i][target];
}
}
// TC: O(nm) // m = target
// SC: O(nm)
// 状态个数(n*target) 乘以每个状态所需的时间O(1)
1:1 翻译成递推
常见变形:
- 至多装capacity, 求方案数/最大价值和
- 恰好装capacity, 求方案数/最大/最小价值和
- 至少装capacity, 求方案数/最小价值和
public class Solution {
public int findTargetSumWays(int[] nums, int S) {
int total = Arrays.stream(nums).sum();
int[][] dp = new int[nums.length][2 * total + 1];
dp[0][nums[0] + total] = 1;
dp[0][-nums[0] + total] += 1;
for (int i = 1; i < nums.length; i++) {
for (int sum = -total; sum <= total; sum++) {
if (dp[i - 1][sum + total] > 0) {
dp[i][sum + nums[i] + total] += dp[i - 1][sum + total];
dp[i][sum - nums[i] + total] += dp[i - 1][sum + total];
}
}
}
return Math.abs(S) > total ? 0 : dp[nums.length - 1][S + total];
}
}