核心思想
01背包：每个物品 要和不要 两种可能性展开
有依赖的背包：多个物品变成一个复合物品（互斥），每件复合物品 不要和怎么要 多种可能性展开 时间复杂度O (物品个数 * 背包容量)，额外空间复杂度O (背包容量)
不能用01背包来解，但是非常重要的问题：非负数组前k个最小的子序列和问题
例题
1、01背包 (模版)
题目描述： 给定一个正数t，表示背包的容量 有n个货物，每个货物可以选择1次 每个货物有自己体积costs[i]和价值values[i] 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大 返回最大的价值
解题思路：
dp [ i ] [ j ]为前i个物品，在花费不超过j的情况下，可以获得的最大价值
这里其实对于每一次的货物，只有选或者不选
dp[i] [j]= dp [i-1] [j] ,不选第i个物品
选择第i个物品的话，如果j>=cost[i] ,dp[i] [j]=dp[i-1] [j-cost[i]]+value[i]
取值，要第i个物品或者不要第i个物品间的较大值
代码如下
package main.java.class073;
import java.io.*;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_01Knapsack
* @description: 01背包(模版)
* // 给定一个正数t，表示背包的容量
* // 有m个货物，每个货物可以选择一次
* // 每个货物有自己的体积costs[i]和价值values[i]
* // 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
* // 返回最大的价值
* // 测试链接 : https://www.luogu.com.cn/problem/P1048
* @author: zs宝
* @create: 2025-08-28 09:08
* @Version 1.0
**/public class Code01_01Knapsack {
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(compute2());
}
out.flush();
out.close();
br.close();
}
//严格按照位置依赖的动态规划
//n个物品编号1~n，第i号物品的花费cost[i]、价值val[i]
//dp[i][j]:表示前i个物品，在花费不超过j的情况下，所能获得的最大价值
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];
//如果要第i个物品，那么必须有
if(j-cost[i]>=0){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-cost[i]]+val[i]);
}
}
}
return dp[n][t];
}
//严格依赖位置的动态规划+空间压缩：根据严格依赖位置的动态规划优化而来
public static int compute2(){
Arrays.fill(dp,0,t+1,0);
for(int i=1;i<=n;i++){
for (int j=t;j>=cost[i];j--){
dp[j]=Math.max(dp[j],dp[j-cost[i]]+val[i]);
}
}
return dp[t];
}
}2、夏季特惠
题目描述： 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有X元的预算，该平台上所有的 n 个游戏均有折扣，标号为 i 的游戏的原价 ai 元，现价只要 bi元（也就是说该游戏可以优惠 ai−bi 元）并且你购买该游戏能获得快乐值为 wi。由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算，但只要满足获得的总优惠金额不低于超过预算的总金额，那在心理上就不会觉得吃亏。现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。
格式：
输入：
- 第一行包含两个数 n 和 X 。
- 接下来 n 行包含每个游戏的信息，原价 ai,现价 bi，能获得的快乐值为 wi 。
输出：
- 输出一个数字，表示你能获得的最大快乐值。示例 1：
输入：
4 100
100 73 60
100 89 35
30 21 30
10 8 10
输出：100
解释：买 1、3、4 三款游戏，获得总优惠 38 元，总金额 102 元超预算 2 元，满足条件，获得 100 快乐值。示例 2：
输入：
3 100
100 100 60
80 80 35
21 21 30
输出：60
解释：只能买下第一个游戏，获得 60 的快乐值。示例 3：
输入：
2 100
100 30 35
140 140 100
输出：135
解释：两款游戏都买，第一款游戏获得优惠 70 元，总开销 170 元，超过预算 70 元，超出预算金额不大于获得优惠金额满足条件，因此可以获得最大快乐值为 135。提示：
所有输入均为整型数
1 <= n <= 5000 <= x <= 10,0000 <= b_i <= a_i <= 5001 <= w_i <= 1,000,000,000关于数据集：
前 30% 的数据， 小数据集 (n<=15)
中间 30% 的数据，中等数据集 (n<=100)
后 40% 的数据，大数据集 (n<=500)
解题思路：
这个题就在于通过获得的总优惠金额不低于超过预算的总金额，那在心理上就不会觉得吃亏，这句话进行转换
将ai-bi-bi<0的物品当作01背包问题，而>0的物品直接买
代码如下
package main.java.class073;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_BuyGoodsHaveDiscount
* @description: 夏季特惠
* // 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏
* // 现在你一共有X元的预算，平台上所有的 n 个游戏均有折扣
* // 标号为 i 的游戏的原价a_i元，现价只要b_i元
* // 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为w_i
* // 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算
* // 只要满足 : 获得的总优惠金额不低于超过预算的总金额
* // 那在心理上就不会觉得吃亏。
* // 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。
* // 测试链接 : https://leetcode.cn/problems/tJau2o/
* @author: zs宝
* @create: 2025-08-28 09:50
* @Version 1.0
**/public class Code02_BuyGoodsHaveDiscount {
public static int MAXN = 501;
public static int MAXX=100001;
public static int n,x,m;
public static int[]cost=new int[MAXN];
public static long[]happies=new long[MAXN];
public static long[]dp=new long [MAXX];
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;
in.nextToken();
x=(int)in.nval;
long ans=0;
m=1;
long happy=0;
for(int i=0,ai,bi,well;i<n;i++){
in.nextToken();
ai=(int)in.nval;
in.nextToken();
bi=(int)in.nval;
in.nextToken();
happy=(long)in.nval;
//这里我么仔细读题意
//总优惠金额不低于超过预算的总金额，那在心理上就不会觉得吃亏
//而在超出预算时的每一件商品，优惠金额=ai-bi,超出金额=bi
//那么只要ai-bi>=bi,则心理上一定不会觉得吃亏,这种就可以为必买，
//那么ai-bi-bi还剩余的值就还能为一种金额，加在总预算上,作为去买其它商品进行心理上的填补（因为我的心里接收程度还剩下一些）
well=ai-bi-bi;
if(well>=0){
ans+=happy;
x+=well;
}else{
//如果ai-bi-bi，即ai-bi<bi,这种游戏就要花费总预算来买
cost[m]=(-well);
happies[m++]=happy;
}
}
//剩余的就是01背包问题
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]]+happies[i]);
}
}
return dp[x];
}
}3、目标和
题目描述： 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数 可以构造一个表达式 例如nums=[2, 1]，可以在2之前添加'+' ，在1之前添加'-' 然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的，运算结果等于 target 的不同表达式的数目
解题思路：
这个题用普通的动态规划甚至暴力递归都可以过
但是这个题在使用动态规划时，dp数组与以往的不同
这个题无法直接看出来可以使用01背包，其转化的思路可以多看看
代码如下
package main.java.class073;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_TargetSum
* @description: 目标和
* // 给你一个非负整数数组 nums 和一个整数 target 。
* // 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数
* // 可以构造一个表达式
* // 例如nums=[2, 1]，可以在2之前添加'+' ，在1之前添加'-'
* // 然后串联起来得到表达式 "+2-1" 。
* // 返回可以通过上述方法构造的，运算结果等于 target 的不同表达式的数目
* // 测试链接 : https://leetcode.cn/problems/target-sum/
* @author: zs宝
* @create: 2025-08-28 10:41
* @Version 1.0
**/public class Code03_TargetSum {
class Solution {
public int findTargetSumWays(int[] nums, int target) {
return findTargetSumWays4(nums,target);
}
/**
暴力递归
*/
public int findTargetSumWays1(int[] nums, int target) {
return f1(nums,target,0,0);
}
public int f1(int[] nums, int target,int i,int j) {
if(i==nums.length){
return j==target?1:0;
}
//要么加，要么减
return f1(nums,target,i+1,j+nums[i])+f1(nums,target,i+1,j-nums[i]);
}
/**
记忆化搜索：有暴力递归优化而来
*/
public int findTargetSumWays2(int[] nums, int target) {
//由于累加和可以i为负数，因此这里不用二维数进行存储，改用hashmap进行存储
//有i位置可以由加，减而来，所以到达这个位置时，之前数字的累加和时不确定的，因此，对于累加和又用了一个hashmap
HashMap<Integer,HashMap<Integer,Integer>>dp=new HashMap<>();
return f2(nums,target,0,0,dp);
}
/**
i:当前位置，第几个数
j:当前数字和
*/
public int f2(int[] nums, int target,int i,int j,HashMap<Integer,HashMap<Integer,Integer>>dp) {
if(i==nums.length){
return j==target?1:0;
}
if(dp.containsKey(i) && dp.get(i).containsKey(j)){
return dp.get(i).get(j);
}
//要么加，要么减
int ans= f2(nums,target,i+1,j+nums[i],dp)+f2(nums,target,i+1,j-nums[i],dp);
dp.putIfAbsent(i,new HashMap<>());
dp.get(i).put(j,ans);
return ans;
}
/**
严格依赖位置的动态规划：由记忆化搜索优化而来
平移技巧 */
public int findTargetSumWays3(int[] nums, int target) {
int n=nums.length;
int sum=0;
for(int i=0;i<n;i++){
sum+=nums[i];
}
if(target<-sum || target>sum){
return 0;
}
int m=2*sum+1;
//由于对于所有的数都可以要么负要么正
//因为有负数，所以我们在记忆化搜索哪里改为了hashmap存储，而不是以往的数组
//现在我们采用平移技巧，即求出数组的最大正和，那么累加和的最大负数将它移到0位置上
//即最大负和+最大正和=0，即所有数字加上数组累加和的值sum
//因此-sum---sum的数变为了0-2*sum,但是有个为0位置，所以最后其实占的空间是0-2*sum+1
int[][]dp=new int[n+1][m];
//原本dp[n][target]=1;平移下
dp[n][target+sum]=1;
for(int i=n-1;i>=0;i--){
for(int j=-sum;j<=sum;j++){
//当前数字有可能是加,不会越界
if(j+nums[i]+sum<m){
dp[i][j+sum]=dp[i+1][j+nums[i]+sum];
}
//当前数字也有可能是减
if(j-nums[i]+sum>=0){
dp[i][j+sum]+=dp[i+1][j-nums[i]+sum];
}
}
}
//原本应该返回dp[0][0],平移
return dp[0][sum];
}
/**
01背包
// 新思路，转化为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 int findTargetSumWays4(int[] nums, int target) {
int n=nums.length;
int sum=0;
for(int i=0;i<n;i++){
sum+=nums[i];
}
if(sum<target || target<-sum || ((target&1)^(sum&1))==1){
return 0;
}
return subset(nums,(target+sum)>>1);
}
// 求非负数组nums有多少个子序列累加和是t
// 01背包问题(子集累加和严格是t) + 空间压缩
// dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
public int subset(int[]nums,int t){
int n=nums.length;
int[]dp=new int[t+1];
dp[0]=1;
for(int i=0;i<n;i++){
for(int j=t;j>=0;j--){
if(j-nums[i]>=0){
dp[j]+=dp[j-nums[i]];
}
}
}
return dp[t];
}
}
}4、最后一块石头的重量Ⅱ
题目描述： 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果
x == y，那么两块石头都会被完全粉碎；如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40] 输出：5
提示：
1 <= stones.length <= 301 <= stones[i] <= 100
解题思路：
这个题有上个题的转化思路非常相似，都是可以将数组拆分为两类
这两类的累加和之差最小为多少
那么就要求这两类都接近数组累加和的一半，急需要找到一组子序列的累加最接近数组累加和的一半
这样就转化为了01背包问题
那些子序列的累加和最接近数组累加和的一半，值为多少。
代码
package main.java.class073;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_LastStoneWeightII
* @description: 最后一块石头的重量 II
* // 有一堆石头，用整数数组 stones 表示
* // 其中 stones[i] 表示第 i 块石头的重量。
* // 每一回合，从中选出任意两块石头，然后将它们一起粉碎
* // 假设石头的重量分别为 x 和 y，且 x <= y
* // 那么粉碎的可能结果如下：
* // 如果 x == y，那么两块石头都会被完全粉碎；
* // 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x
* // 最后，最多只会剩下一块 石头，返回此石头 最小的可能重量
* // 如果没有石头剩下，就返回 0
* // 测试链接 : https://leetcode.cn/problems/last-stone-weight-ii/
* @author: zs宝
* @create: 2025-09-01 10:48
* @Version 1.0
**/public class Code04_LastStoneWeightII {
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int stone:stones){
sum+=stone;
}
int target=sum/2;
int sub=subset(stones,target);
return sum-sub-sub;
}
//找出在stones的子序列中，最接近target的子序列和
public int subset(int[] stones,int target){
int n=stones.length;
//dp[j]子序列累加和最接近j的值是多少
int[]dp=new int[target+1];
for(int i=0;i<n;i++){
for(int j=target;j>=0;j--){
if(j-stones[i]>=0){
dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
}
return dp[target];
}
}
}5、有依赖的背包 (模版)
题目描述：
物品分为两大类：主件和附件 主件购买没有限制，钱够就可以；附件购买有限制，该附件所归属的主件先购买，才能购买这个附件
例如，若想买打印机或扫描仪这样的附件，必须先购买电脑这个主件。
以下是一些主件及其附件的展示： 电脑：打印机，扫描仪 | 书柜：图书 | 书桌：台灯，文具 | 工作椅：无附件
每个主件最多有2个附件，并且附件不会再有附件，主件购买后，怎么去选择归属附件完全随意，钱够就可以 所有的物品编号都在1~m之间，每个物品有三个信息：价格v、重要度p、归属q 价格就是花费，价格 * 重要度 就是收益，归属就是该商品是依附于哪个编号的主件 比如一件商品信息为[300,2,6]，花费300，收益600，该商品是6号主件商品的附件 再比如一件商品信息[100,4,0]，花费100，收益400，该商品自身是主件 (q==0) 给定m件商品的信息，给定总钱数n，返回在不违反购买规则的情况下最大的收益
测试链接 : https://www.luogu.com.cn/problem/P1064
测试链接 : https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
解题思路：
这个题相比我们之前做的01背包，多了依赖的选项
只有买了主件才可以买附件，即附件的买或者不买多了一个主件的购买条件依赖
因此我们在讨论时，只能从主件开始讨论，在讨论主件时再讨论附件是否购买
而对于是否购买这一块就几乎和01背包问题十分类似了，要或者不要
代码如下
package main.java.class073;
import java.io.*;
import java.security.PublicKey;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_DependentKnapsack
* @description: 有依赖的背包(模版)
* // 物品分为两大类：主件和附件
* // 主件的购买没有限制，钱够就可以；附件的购买有限制，该附件所归属的主件先购买，才能购买这个附件
* // 例如，若想买打印机或扫描仪这样的附件，必须先购买电脑这个主件
* // 以下是一些主件及其附件的展示：
* // 电脑：打印机，扫描仪 | 书柜：图书 | 书桌：台灯，文具 | 工作椅：无附件
* // 每个主件最多有2个附件，并且附件不会再有附件，主件购买后，怎么去选择归属附件完全随意，钱够就可以
* // 所有的物品编号都在1~m之间，每个物品有三个信息：价格v、重要度p、归属q
* // 价格就是花费，价格 * 重要度 就是收益，归属就是该商品是依附于哪个编号的主件
* // 比如一件商品信息为[300,2,6]，花费300，收益600，该商品是6号主件商品的附件
* // 再比如一件商品信息[100,4,0]，花费100，收益400，该商品自身是主件(q==0)
* // 给定m件商品的信息，给定总钱数n，返回在不违反购买规则的情况下最大的收益
* // 测试链接 : https://www.luogu.com.cn/problem/P1064
* // 测试链接 : https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
* @author: zs宝
* @create: 2025-09-01 11:12
* @Version 1.0
**/public class Code05_DependentKnapsack {
public static int MAXN = 32001;
public static int MAXM = 61;
//储存物品的价格
public static int[] cost = new int[MAXM];
//存储物品的价值，价格*重要程度
public static int[] val = new int[MAXM];
//判断一个物品是否是主件
public static boolean[] king = new boolean[MAXM];
//存储主件的附件个数
public static int[] fans = new int[MAXM];
//存储主件的附件有哪些
public static int[][] follows = new int[MAXM][2];
//dp数组
public static int[] dp = new int[MAXN];
public static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(buffer);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
in.nextToken();
m = (int) in.nval;
clean();
for (int i = 1, vi, pi, qi; i <= m; i++) {
in.nextToken();
vi = (int) in.nval;
in.nextToken();
pi = (int) in.nval;
in.nextToken();
qi = (int) in.nval;
cost[i] = vi;
val[i] = vi * pi;
king[i] = qi == 0;
if (qi != 0) {
follows[qi][fans[qi]++] = i;
}
}
out.println(compute1());
}
out.flush();
out.close();
buffer.close();
}
public static void clean() {
for (int i = 0; i <= m; i++) {
fans[i] = 0;
}
}
/**
* 严格依赖位置的动态规划，有01背包的思想，但有不完全是
*
* @return
*/
public static int compute1() {
//dp[i][j]:前i件物品，花费不超过j的所能得到的最大价值
int[][] dp = new int[m + 1][n + 1];
//专门记录前一个主件的的位置，初始化为0，因为没有那台机器的主机序列为0，因此当为0时，dp[0]=0;
int q = 0;
for (int i = 1, fan1, fan2; i <= m; i++) {
//只有当是主件的时候我们才开始计算
if (king[i]) {
for (int j = 0; j <= n; j++) {
//初始化为不买当前主件的时候
dp[i][j] = dp[q][j];
//接下来开始讨论
//买主件，买主件+一个附件，买主件+2个附件
//只买一个主件时
if (j - cost[i] >= 0) {
dp[i][j] = Math.max(dp[i][j], dp[q][j - cost[i]] + val[i]);
}
//开始考虑附件的时候
fan1 = fans[i] >= 1 ? follows[i][0] : -1;
fan2 = fans[i] >= 2 ? follows[i][1] : -1;
//主件加一个附件
if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {
dp[i][j] = Math.max(dp[i][j], dp[q][j - cost[i] - cost[fan1]] + val[i] + val[fan1]);
}
if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {
dp[i][j] = Math.max(dp[i][j], dp[q][j - cost[i] - cost[fan2]] + val[i] + val[fan2]);
}
//主件+2附件
if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0) {
dp[i][j] = Math.max(dp[i][j], dp[q][j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);
}
}
q = i;
}
}
//注意是，返回遍历到的最后一个主件，不能是dp[m][n]，m可能是个附件，根本不会往哪里走
return dp[q][n];
}
//动态规划+空间压缩
public static int compute2() {
Arrays.fill(dp, 0, n + 1, 0);
for (int i = 1, fan1, fan2; i <= m; i++) {
if (king[i]) {
for (int j = n; j >= 0; j--) {
//接下来开始讨论
//买主件，买主件+一个附件，买主件+2个附件
//只买一个主件时
if (j - cost[i] >= 0) {
dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);
}
//开始考虑附件的时候
fan1 = fans[i] >= 1 ? follows[i][0] : -1;
fan2 = fans[i] >= 2 ? follows[i][1] : -1;
//主件加一个附件
if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {
dp[j] = Math.max(dp[j], dp[j - cost[i] - cost[fan1]] + val[i] + val[fan1]);
}
if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {
dp[j] = Math.max(dp[j], dp[j - cost[i] - cost[fan2]] + val[i] + val[fan2]);
}
//主件+2附件
if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0) {
dp[j] = Math.max(dp[j], dp[j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);
}
}
}
}
return dp[n];
}
}6、非负数组前k个最小的子序列累加和
给定一个数组nums，含有n个数字，都是非负数 给定一个正数k，返回所有子序列中累加和最小的前k个累加和 子序列是包含空集的 1 <= n <= 10^5 1 <= nums[i] <= 10^6 1 <= k <= 10^5 注意这个数据量，用01背包的解法是不行的，时间复杂度太高了 对数器验证
时间复杂度O (nlogn) + O (klogk)，额外空间复杂度O (k)
注意：这个题使用01背包大概率过不了，这个题既不能用01背包，也不属于有依赖的背包问题
解题思路：
01背包
计算数组总和
sum。定义 dp[j] =子序列凑出累加和为j的数量。
遍历每个 num，更新 dp。
从小到大遍历所有 j，依次把能形成的 j 放入答案，直到取够 k 个
小根堆
将数组从小到大排序
小根堆中加入数组，数组表示｛当前第i个元素，累加和｝
由于数组是从小大大排序的，因此每次新加入的元素都要比当前弹出的位置的元素大，这就对加入元素的方式有要求
每次加i的下一个位置的元素时，新进堆的数组的累加和都必加上nums[i+1]
所以对于子序列的讨论要或者不要，都集中在每次弹出的堆顶元素上，也就是i要不要
拿到前k个弹出数组中定义的累加和即可
代码如下
package main.java.class073;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code06_TopKMinimumSubsequenceSum
* @description: 非负数组前k个最小的子序列累加和
* // 给定一个数组nums，含有n个数字，都是非负数
* // 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
* // 子序列是包含空集的
* // 1 <= n <= 10^5
* // 1 <= nums[i] <= 10^6 * // 1 <= k <= 10^5 * // 注意这个数据量，用01背包的解法是不行的，时间复杂度太高了
* // 对数器验证
* @author: zs宝
* @create: 2025-09-02 10:19
* @Version 1.0
**/public class Code06_TopKMinimumSubsequenceSum {
// 01背包来实现
// 这种方法此时不是最优解
// 因为n很大，数值也很大，那么可能的累加和就更大
// 时间复杂度太差
public static int[] topKSum2(int[] nums, int k) {
int sum=0;
for(int num:nums){
sum+=num;
}
//dp[i][j]表示前i个数，累加和为j的子序列数量有多少
//这里我们用一维进行空间压缩
int[]dp=new int[sum+1];
//无论怎样都有一个空集，累加和为0
dp[0]=1;
for(int num:nums){
for(int j=sum;j>=num;j--){
//注意这里统计的是数量
dp[j]+=dp[j-num];
}
}
//然后寻找累加和最小的前k个
int []ans=new int[k];
int index=0;
for(int j=0;j<=sum && index<k;j++){
//注意这里每一个累加和的值都有可能有多个，数量存储在dp[j]中
for(int i=0;i<dp[j] && index<k;i++){
ans[index++]=j;
}
}
return ans;
}
// 正式方法
// 用堆来做是最优解，时间复杂度O(n * log n) + O(k * log k)
public static int[] topKSum3(int[] nums, int k) {
Arrays.sort(nums);
//小顶堆
//堆中存放的元素是，到达i下标时的某一个子序列的累加和
PriorityQueue<int[]>heap=new PriorityQueue<>((a,b)->a[1]-b[1]);
heap.add(new int[]{0,nums[0]});
int[]ans=new int[k];
//初始化已经有了一个空集在其中，所以从1开始计数
for(int i=1,right,sum;i<k;i++){
//小顶堆堆顶元素弹出
int[] cur = heap.poll();
right=cur[0];
sum=cur[1];
ans[i]=sum;
//由于是子序列，所以就会有当前元素要或者不要
if(right+1<nums.length){
//当前right元素要
heap.add(new int[]{right+1,sum+nums[right+1]});
//当前right元素不要
//因为我们的数组nums是经过排序的，因此sum-nums[right]+nums[right+1]一定大于原本的sum
heap.add(new int[]{right+1,sum-nums[right]+nums[right+1]});
}
}
return ans;
}
// 暴力方法
// 为了验证
public static int[] topKSum1(int[] nums, int k) {
ArrayList<Integer> allSubsequences = new ArrayList<>();
f1(nums, 0, 0, allSubsequences);
allSubsequences.sort((a, b) -> a.compareTo(b));
int[] ans = new int[k];
for (int i = 0; i < k; i++) {
ans[i] = allSubsequences.get(i);
}
return ans;
}
// 暴力方法
// 得到所有子序列的和
public static void f1(int[] nums, int index, int sum, ArrayList<Integer> ans) {
if (index == nums.length) {
ans.add(sum);
} else {
f1(nums, index + 1, sum, ans);
f1(nums, index + 1, sum + nums[index], ans);
}
}
// 为了测试
public static int[] randomArray(int len, int value) {
int[] ans = new int[len];
for (int i = 0; i < len; i++) {
ans[i] = (int) (Math.random() * value);
}
return ans;
}
// 为了测试
public static boolean equals(int[] ans1, int[] ans2) {
if (ans1.length != ans2.length) {
return false;
}
for (int i = 0; i < ans1.length; i++) {
if (ans1[i] != ans2[i]) {
return false;
}
}
return true;
}
// 为了测试
// 对数器
public static void main(String[] args) {
int n = 15;
int v = 40;
int testTime = 5000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * n) + 1;
int[] nums = randomArray(len, v);
int k = (int) (Math.random() * ((1 << len) - 1)) + 1;
int[] ans1 = topKSum1(nums, k);
int[] ans2 = topKSum2(nums, k);
int[] ans3 = topKSum3(nums, k);
if (!equals(ans1, ans2) || !equals(ans1, ans3)) {
System.out.println("出错了！");
}
}
System.out.println("测试结束");
}
}