DP 背包 - wenzhoullq/leetcode GitHub Wiki
分析
背包问题的核心是，对每一个品种，在资源个数dp[i][j]中的i和背包体积dp[i][j]中的j和最小满足（最小满足是dp[i][j]的值）的约束下进行，先对资源种类进行遍历，再对背包体积进行遍历；既有j的约束又有dp[i][j]的约束。
核心的转移方程是： dp[i][j]=dp[i-1][j](截至品种i-1的所拥有的，其中不加入品种i)+(这里的+不一定是+，可能是||操作)dp[i-1][j-v](截至i-1品种+i品种的);，同时我们能看出这么一种思想：类同于股票题，是选择（买）和不选择（不买）之间的转移方程；
于是出题就出现了这样思考方式：品种的遍历可以是出题点;资源的限制是出题点:资源的限制直接决定了买的方式：资源无限是完全背包问题，资源有限是01背包问题，资源无限的完全背包问题的选择，完全背包+01背包的混合；加不加入dp[i-1][j]的出题点；再增加一个附加值价值是出题点（三维）;恰好有/至少有/无要求也是出题点，恰好有与continue有关，至少有需要一个max函数，
如果当背包的体积过大的时候，开数组（即使用了滚动数组）也会mle，这时候需要考虑使用map
关键词
组合数，方案数，这里有一种思想，一般来说，只要是有背包的形式（种类+体积）都是可以用背包的模板来做；
还有个比较重要的是排列数和组合数的区别，比如说跳楼梯这种，跳到三层，先1再跳2和先跳2再跳1是不同的方法，而取硬币组合成3块，先取2块再取1块和先取1块再取2块是一样的方法；排列数的值大于组合数的值，而先规定硬币的顺序可以排除相同组合的重复
统一模板
int[][] dp=new int[k+1][v+1];//i是品种数，j是背包体积数
for(int i=0;i<j;i++) dp[0][nums[0]]=1;//初始化第0行
for(int i=1;i<=k;i++){//先对品种数进行遍历
for(int j=0;j<=v;j++){//对于背包的体积进行遍历, j=0是比较容易遗漏的点
if(体积<品种所具备的资源||前面的组合无法构成) continue;//||后面部分值得思考
//根据题目类型进行操作
}
}
01背包问题 (有限个也算01背包问题)
模板
注：如果数量有2000个的话，枚举必超时，因此需要优化，把个数优化成1个，2个，4个这样的二进制，这可以表达所有的数字，如果减完之后的s还不为0的话,则再新增一个s，这样就转化为0-1背包问题了
int[] dp=new int[v+1];//i是品种数，j是背包体积数
Arrays.fill(dp,-1);对第0行进行初始化
dp[0]=0;
for(int i=1;i<k;i++){//先各个品种数进行遍历
for(int k=1;k<= num;k++){//如果存在次数，先对次数遍历
for(int j=v;j>=0;j--){//对于背包的体积进行遍历
if(j<nums[i]) continue;//排除不符合的
if(dp[i-1][j-nums[i-1]]!=-1)
dp[i][j]= Math.max(dp[i][j],dp[i-1][j-nums[i-1]]+);//一般考虑max形式，这样无论是资源还是什么都是通用模板
}
}
return dp[i][j];
}
题目
P2946 [USACO09MAR]Cow Frisbee Team S
1049. 最后一块石头的重量 II这题推出01背包问题的思路比较有意思，因为可以放回，所以我把分为两部分，一部分是小于一半中找到最大的，然后总量-小于一半的最大的*2即可
完全背包问题
资源是大于1的
模板
资源是无限的
int[] dp=new int[v+1];//i是品种数，j是背包体积数
Arrays.fill(dp,-1);//对第0行初始化
dp[0]=0;
for(int i=1;i<=n;i++){//先对品种数进行遍历
for(int j=0;j<=v;j++){//对于背包的体积进行遍历
if(j<nums[i-1]) continue;
if(dp[j-nums[i-1]]!=-1)
dp[j]=Math.max(dp[j],dp[j-nums[i-1]]+);
}
}
题目
322. 零钱兑换 用排列数来做更快
1449. 数位成本和为目标值的最大数字 恰好用完这个出题点值得琢磨
多维背包问题
涉及到多个维度的背包问题,比如说一个维度是体积，那么这里多一个维度体力，别的都是一样的
题目
题目
P1541 [NOIP2010 提高组] 乌龟棋 也是根据资源进行更新的
AcWing 603. 打怪兽 三维，但是可以降低到二维
混合背包问题
0-1背包和完全背包的混合体，只需将他们分成不同组即可
题目
分组背包题
先将物品分组，再通过组别-容量-个体进行遍历，用二维比价好，一维老是容易出各种问题
int m = in.nextInt(),n=in.nextInt();
int[][][] arr = new int[m+1][m+1][2];//0是体积,1是收益
int[] team = new int[m+1];
for( int i=1;i<=m;i++){
int t= in.nextInt(),v=in.nextInt(),p=in.nextInt();
team[t]++;
arr[t][team[t]][0] = v;
arr[t][team[t]][1] = p;
}
int[] dp =new int[n+1];
Arrays.fill(dp,-1);
dp[0]=0;
int ans=0;
for(int t=1;t<=m;t++){//遍历组，只能选一个
for(int j=n;j>=0;j--){//遍历体积，倒叙，这样就不会在同一个组里选到多个
for(int k=1;k<=team[t];k++){//遍历组里的物品
if(j<arr[t][k][0]) continue ;
if(dp[j-arr[t][k][0]]!=-1){
dp[j]=Math.max(dp[j],dp[j-arr[t][k][0]]+arr[t][k][1]);
ans=Math.max(ans,dp[j]);
}
}
}
}
System.out.println(ans);
题目
品种遍历题
主要在于品种的遍历以及对dp的设计
题目
不加入dp[i-1][v]
不能加入原dp[i-1][v],即不能出现不要i品种只要截止i-1的，要分析出这一点，并且对于这种的话dp[i][0]就不需要赋值初始化了，并且在dp[i][j]+=dp[i-1][j-nums[i-1]];上抄录的是上一层
题目
1269. 停在原地的方案数 (因为需要返回，所以注意优化方法
附加价值
题目
879. 盈利计划 这题非常的精妙，主要体现在至少这个词
原题
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
这里最为精妙的是至少产生这一词，一般来说都是恰好为target，而这里使用了至少，那我们应该如何设置dp呢？ dp[i][j][k] 三维度分别进行到第i项目，有j个人，利润至少为k，这个设计非常的精妙，以往设置的都是恰好为k,如果k<profit[i-1]的话需要排除的，因为不可能存在负利润，而这个至少为k的话是可能出现负利润的情况：是因为k是最小值，而实际上的值可能是大于K的,但是下标又不能为负数，因此出现了转换Math.max(k-profit[i-1],0);这也是本题的精华所在。