073背包dp-01背包 有依赖的背包

01背包:每个背包要与不要两种可能性展开
有依赖的背包:多个物品变成一个复合物品(互斥)，每件复合物品要和怎么要多种可能性展开
不能用01背包来解，但是非常重要的问题：非负数组前k个最小的子序列和问题

题目一

class Main {

	public static int MAXM = 101;
	public static int MAXT = 1001;
	public static int[] cost = new int[MAXM];
	public static int[] val = new int[MAXM];
	public static int[] dp = new int[MAXT];
	public static int t, n;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			t = (int) in.nval;
			in.nextToken();
			n = (int) in.nval;
			for (int i = 1; i <= n; i++) {
				in.nextToken();
				cost[i] = (int) in.nval;
				in.nextToken();
				val[i] = (int) in.nval;
			}
			out.println(compute1());
		}
		out.flush();
		out.close();
		br.close();
	}

	// 严格位置依赖的动态规划
	// n个物品编号1~n，第i号物品的花费cost[i]、价值val[i]
	// cost、val数组是全局变量，已经把数据读入了
	public static int compute1() {
		int[][] dp = new int[n + 1][t + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= t; j++) {
				// 不要i号物品
				dp[i][j] = dp[i - 1][j];
				if (j - cost[i] >= 0) {
					// 要i号物品
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost[i]] + val[i]);
				}
			}
		}
		return dp[n][t];
	}
}

题目二

// 夏季特惠
// 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏
// 现在你一共有X元的预算，平台上所有的 n 个游戏均有折扣
// 标号为 i 的游戏的原价a_i元，现价只要b_i元
// 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为w_i
// 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算
// 只要满足 : 获得的总优惠金额不低于超过预算的总金额
// 那在心理上就不会觉得吃亏。
// 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。
// 测试链接 : https://leetcode.cn/problems/tJau2o/

public class Main {

	public static int MAXN = 501;

	public static int MAXX = 100001;

	// 对于"一定要买的商品"，直接买！
	// 只把"需要考虑的商品"放入cost、val数组
	public static int[] cost = new int[MAXN];

	public static long[] val = new long[MAXN];

	public static long[] dp = new long[MAXX];

	public static int n, m, x;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			m = 1;
			in.nextToken();
			x = (int) in.nval;
			long ans = 0;
			long happy = 0;
			for (int i = 1, pre, cur, well; i <= n; i++) {
				// 原价
				in.nextToken(); pre = (int) in.nval;
				// 现价
				in.nextToken(); cur = (int) in.nval;
				// 快乐值
				in.nextToken(); happy = (long) in.nval;
				well = pre - cur - cur;
				// 如下是一件"一定要买的商品"
				// 预算 = 100，商品原价 = 10，打折后 = 3
				// 那么好处(well) = (10 - 3) - 3 = 4
				// 所以，可以认为这件商品把预算增加到了104！一定要买！
				// 如下是一件"需要考虑的商品"
				// 预算 = 104，商品原价 = 10，打折后 = 8
				// 那么好处(well) = (10 - 8) - 8 = -6
				// 所以，可以认为这件商品就花掉6元！
				// 也就是说以后花的不是打折后的值，是"坏处"
				if (well >= 0) {
					x += well;
					ans += happy;
				} else {
					cost[m] = -well;
					val[m++] = happy;
				}
			}
			ans += compute();
			out.println(ans);
		}
		out.flush();
		out.close();
		br.close();
	}

	public static long compute() {
		Arrays.fill(dp, 0, x + 1, 0);
		for (int i = 1; i <= m; i++) {
			for (int j = x; j >= cost[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);
			}
		}
		return dp[x];
	}

}

题目三

import java.util.HashMap;

// 目标和
// 给你一个非负整数数组 nums 和一个整数 target 。
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数
// 可以构造一个表达式
// 例如nums=[2, 1]，可以在2之前添加'+' ，在1之前添加'-'
// 然后串联起来得到表达式 "+2-1" 。
// 返回可以通过上述方法构造的，运算结果等于 target 的不同表达式的数目


class Solution {
       // 新思路，转化为01背包问题
	// 思考1:
	// 虽然题目说nums是非负数组，但即使nums中有负数比如[3,-4,2]
	// 因为能在每个数前面用+或者-号
	// 所以[3,-4,2]其实和[3,4,2]会达成一样的结果
	// 所以即使nums中有负数，也可以把负数直接变成正数，也不会影响结果
	// 思考2:
	// 如果nums都是非负数，并且所有数的累加和是sum
	// 那么如果target>sum，很明显没有任何方法可以达到target，可以直接返回0
	// 思考3:
	// nums内部的数组，不管怎么+和-，最终的结果都一定不会改变奇偶性
	// 所以，如果所有数的累加和是sum，并且与target的奇偶性不一样
	// 那么没有任何方法可以达到target，可以直接返回0
	// 思考4(最重要):
	// 比如说给定一个数组, nums = [1, 2, 3, 4, 5] 并且 target = 3
	// 其中一个方案是 : +1 -2 +3 -4 +5 = 3
	// 该方案中取了正的集合为A = {1，3，5}
	// 该方案中取了负的集合为B = {2，4}
	// 所以任何一种方案，都一定有 sum(A) - sum(B) = target
	// 现在我们来处理一下这个等式，把左右两边都加上sum(A) + sum(B)，那么就会变成如下：
	// sum(A) - sum(B) + sum(A) + sum(B) = target + sum(A) + sum(B)
	// 2 * sum(A) = target + 数组所有数的累加和
	// sum(A) = (target + 数组所有数的累加和) / 2
	// 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
	// 那么就一定对应一种target的方式
	// 比如非负数组nums，target = 1, nums所有数累加和是11
	// 求有多少方法组成1，其实就是求，有多少种子集累加和达到6的方法，(1+11)/2=6
	// 因为，子集累加和6 - 另一半的子集累加和5 = 1(target)
	// 所以有多少个累加和为6的不同集合，就代表有多少个target==1的表达式数量
	// 至此已经转化为01背包问题了
	public static int findTargetSumWays(int[] nums, int target) {
		int sum = 0;
		for (int n : nums) {
			sum += n;
		}
		if (sum < target || ((target & 1) ^ (sum & 1)) == 1) {
			return 0;
		}
		return subsets(nums, (target + sum) >> 1);
	}

	// 求非负数组nums有多少个子序列累加和是t
	// 01背包问题(子集累加和严格是t) + 空间压缩
	// dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
	public static int subsets(int[] nums, int t) {
		if (t < 0) {
			return 0;
		}
		int[] dp = new int[t + 1];
		dp[0] = 1;
		for (int num : nums) { // i省略了
			for (int j = t; j >= num; j--) {
				dp[j] += dp[j - num];
			}
		}
		return dp[t];
	}

}