从动态规划专题 中抽取出来的
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
样例
样例 1 : 输入: [3 ,4 ,8 ,5 ], backpack size=10 输出: 9 样例 2 : 输入: [2 ,3 ,5 ,7 ], backpack size=12 输出: 12
挑战
解法一
记忆化递归，对于每个元素，有两种选择，装或者不装
int [][] cache=null ; public int backPack2 (int m,int [] A) cache=new int [A.length+1 ][m+1 ]; for (int i=0 ;i<A.length;i++) { Arrays.fill(cache[i],-1 ); } if (A==null || A.length<=0 ) { return 0 ; } return putPack(m,A,A.length-1 ); } public int putPack (int m,int [] A,int index) if (index<0 || m<=0 ) { return 0 ; } if (cache[index][m]!=-1 ) { return cache[index][m]; } int res=putPack(m,A,index-1 ); if (A[index]<=m) { res=Math.max(res,A[index]+putPack(m-A[index],A,index-1 )); } cache[index][m]=res; return res; }
暴力递归的时间复杂度将会是O((2^N)*N)
其实整个递归的思路是很清晰明白的，对于每个元素，有两种情况，这也是之所以称之为0-1背包的原因
不选的话，背包的容量不变，改变为问题putPack(m,A,index-1)
选的话，背包的容量变小，改变为问题putPack(m-A[index],A,index-1)+A[index]
到底选还是不选，取决于两种方案哪一种更好，我们要求的，就是这个最好的方案，知道了这样的递推关系后我们就可以很容易的写出递归方程，这里在递归的过程中有可能会产生重叠的子问题（其实这里我还纠结了好一会儿，我一直感觉没有重叠的子问题，后来画一下递归树就明白了，只是重叠的不明显），所以我们可以通过缓存每次计算的结果来进行记忆化递归，整体的时间复杂度应该是O(2^N)，空间O(M*N)显然不是我们想要的结果
这里一开始我是想用Integer[][]的数组，然后就不用赋初始值，判断不为null就行，结果空间溢出了。。。lintCode好严格，换成int[][]然后赋个初始值就过了
解法二
动态规划解法，在讲解之前，我们用一个二维表来分析下整个递推的过程
物品列表（样例1），因为这题价值就是重量，所以w和v是一样的
DpTable（样例1）
一行一行的看，从左到右，dp[index][m]代表 背包总容量不超过m的情况下，考虑装入[0,index]中的元素能获得最大收益 ，比如dp[1][7]代表的就是背包总容量不超过7的情况下，考虑装入[0,1] 范围内的元素所能获得的最大收益，人脑思考结果自然是7了，下面我们分析下如果dp推出这个结果
前面我们已经分析过0-1背包的递归过程，每个元素面临两个选择，这里也一样
dp[1][7]如果我们选择不装入当前index位置的元素的话，那么最大收益就是dp[0][7]=3这一点应该没啥疑问
如果我们考虑装入当前index位置的元素的话，m肯定会减小，那么所获得的最大收益就应该是A[index]+dp[0][7-4]=7
注意这里当前index的值都是依赖于上一层index-1的计算结果的，也就是依赖于上一次m,[0,index-1]最大值的结果，所以我们需要手动的初始化第一层的值）
最后我们得到的核心状态方程就是下面这样的
dp[index][m]=max(dp[index-1][m],A[index]+dp[index-1][j-A[index]])
然后我们根据这个很容易就可以写出dp的解法
public int backPack (int m,int [] A) if (A==null || A.length<=0 ) { return 0 ; } int [][] dp=new int [A.length][m+1 ]; for (int i=0 ;i<A.length;i++) { for (int j=0 ;j<=m;j++) { if (j==0 ) { dp[i][j]=0 ; }else if (i==0 ) { dp[i][j]=j-A[i]>=0 ?A[i]:0 ; }else if (i>0 ) { dp[i][j]=j-A[i]>=0 ?Math.max(dp[i-1 ][j],dp[i-1 ][j-A[i]]+A[i]):dp[i-1 ][j]; } } } return dp[A.length-1 ][m]; }
当然我们肯定是不满足于这种二维的dp的，所以我们还得优化下空间，这里每一层都只依赖于上一层的结果，所以我么很容易就可以改成一维的，当然这里还有个小坑，如果直接按照上面的代码来改的话就是错的，我们先看看正确的改法
public int backPack4 (int m,int [] A) if (A==null || A.length<=0 ) { return 0 ; } int [] dp=new int [m+1 ]; for (int i=0 ;i<A.length;i++) { for (int j=m;j>=0 ;j--) { if (j==0 ) { dp[j]=0 ; }else if (i==0 ) { dp[j]= j-A[i]>=0 ?A[i]:0 ; }else { dp[j]=j-A[i]>=0 ?Math.max(dp[j],dp[j-A[i]]+A[i]):dp[j]; } } } return dp[m]; }
可以看到，我们的内层循环不再是从左往右，而是从右往左，这样的好处就是避免了dp[j-A[i]]已经被当前内层循环前面的元素 覆盖的尴尬情况，结合上面的表推一下就知道了
解法三
算是对之前代码的优化吧，之前写的乱七八糟的
public int backPack (int m,int [] A) if (A==null || A.length<=0 ) { return 0 ; } int [] dp=new int [m+1 ]; for (int i=0 ;i<A.length;i++) { for (int j=m;j>=A[i];j--) { dp[j]=Math.max(dp[j],dp[j-A[i]]+A[i]); } } return dp[m]; }
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输入格式
第一行两个整数，N，V用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000
输入样例
输出样例：
解法一
相比01背包交换了内循环的顺序就ok了，当然也可以将每个物品拆分，不过复杂度会变高
import java.util.*;public class Main public static void main (String[] args) Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int V=sc.nextInt(); int [] dp=new int [V+1 ]; for (int i=0 ;i<N;i++){ int vi=sc.nextInt(); int wi=sc.nextInt(); for (int j=vi;j<=V;j++) { dp[j]=Math.max(dp[j],dp[j-vi]+wi); } } System.out.println(dp[V]); } }
其实这个结论要直接理解还是有点难懂的，具体的推导过程可以看下面的 零钱兑换
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1 , 5 , 11 , 5 ] 输出: true 解释: 数组可以分割成 [1 , 5 , 5 ] 和 [11 ].
示例 2:
输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
解法一
现在递归写起来已经有点感觉了，类似的题基本上都能写出记忆化递归的方法来
Boolean[][] cache=null ; public boolean canPartition (int [] nums) if (nums==null || nums.length<=0 ) return false ; int sum=0 ; for (int e:nums) sum+=e; cache=new Boolean[nums.length][sum+1 ]; if (sum%2 !=0 ) { return false ; } return partition(nums,0 ,0 ,sum/2 ); } public boolean partition (int [] nums,int index,int half,int sum) if (index==nums.length) { return false ; } if (cache[index][half]!=null ) { return cache[index][half]; } if (half==sum) { return true ; } cache[index][half]=partition(nums,index+1 ,half,sum) || (half<sum&&partition(nums,index+1 ,half+nums[index],sum)); return cache[index][half]; }
解法二
动态规划，依然是典型的背包问题，可以理解为用nums中的元素，填满sum/2容量大小的背包，递推公式
dp[i][j] =dp[i-1][j] || dp[i-1][j-nums[i]] 选当前元素和不选当前元素，有一个能填满就ok
dp[i][j] 含义为：考虑[0,i] 范围内的元素，能否恰好装满 j大小的容器
public boolean canPartition (int [] nums) if (nums==null || nums.length<=0 ) return false ; int sum=0 ; for (int e:nums) sum+=e; if (sum%2 !=0 ) { return false ; } int half=sum/2 ; boolean [][] dp=new boolean [nums.length][half+1 ]; for (int j=0 ;j<=half;j++) { dp[0 ][j]= nums[0 ]==j; } for (int i=1 ;i<nums.length;i++) { for (int j=0 ;j<=half;j++) { dp[i][j]= j>=nums[i]?dp[i-1 ][j] || dp[i-1 ][j-nums[i]]:dp[i-1 ][j]; } if (dp[i][half]) { return true ; } } return dp[nums.length-1 ][half]; }
空间上的优化
public boolean canPartition (int [] nums) if (nums==null || nums.length<=0 ) return false ; int sum=0 ; for (int e:nums) sum+=e; if (sum%2 !=0 ) { return false ; } int half=sum/2 ; boolean [] dp=new boolean [half+1 ]; for (int j=0 ;j<=half;j++) { dp[j]= nums[0 ]==j; } for (int i=1 ;i<nums.length;i++) { for (int j=half;j>=nums[i];j--) { dp[j]=dp[j]||dp[j-nums[i]]; } if (dp[half]) { return true ; } } return dp[half]; }
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1 , 2 , 5 ], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2 ], amount = 3 输出: -1
说明:
解法一
其实就是dfs，我最开始就是写的dfs只不过时间复杂度太高，没做记忆化，这里其实一开始做了记忆化也一直没跑过，一直超时，最后给的case是6249 好像也不算很大吧，然后我后来把fill 填充数组删了，用Integer就跑过了。。。
private Integer[] cache=null ;public int coinChange2 (int [] coins,int amount) cache=new Integer[amount+1 ]; return takeCoins(coins,amount); } public int takeCoins (int [] coins, int amount) if (amount==0 ) { return 0 ; } if (cache[amount]!=null ) { return cache[amount]; } int res=Integer.MAX_VALUE; for (int i=0 ;i<coins.length;i++) { if (amount<coins[i]) continue ; int sub=takeCoins(coins,amount-coins[i]); if (sub!=-1 ) { res=Math.min(sub+1 ,res); } } cache[amount]= res==Integer.MAX_VALUE?-1 :res; return cache[amount]; }
解法二
动态规划，二维dp，注意这里其实和前面的背包问题就有区别了，这里实际上就是个无限背包问题，因为这里的硬币是无限的，每个面值的硬币都可以重复的选取
DPTable
状态定义
这里dp[i][j] 的含义为：考虑[0，i] 范围内的元素，能凑成 j 所需的最少硬币数 ，和之前的01背包问题状态定义没什么区别
状态方程
首先明确一点，这里我们对第coins[i]个硬币有两种选择
不拿
拿，拿1~k个(k为硬币个数的限制，这里没有限制，所以是无穷大)
进而我们可以的到状态转移的方程：
f[i][j] = min(f[i-1][j], f[i-1][j-c]+1, f[i-1][j-2*c]+2, ..., f[i-1][j-k*c]+k)
但是这个方程有很多计算是重复的
f[i][j-c]=min(f[i-1][j-c], f[i-1][j-2*c]+1, ..., f[i-1][j-k*c]+k-1)
两者合并得到
f[i][j] = min(f[i-1]f[j], f[i][j-c]+1) 有了状态方程，代码就好写了
public int coinChange4 (int [] coins,int amount) int [][] dp=new int [coins.length][amount+1 ]; for (int j=0 ;j<=amount;j++) { dp[0 ][j]=j%coins[0 ]==0 ?j/coins[0 ]:Integer.MAX_VALUE; } for (int i=1 ;i<coins.length;i++) { for (int j=0 ;j<=amount;j++) { if (j<coins[i] || dp[i][j-coins[i]]==Integer.MAX_VALUE) { dp[i][j]=dp[i-1 ][j]; }else { dp[i][j]=Math.min(dp[i][j-coins[i]]+1 ,dp[i-1 ][j]); } } } return dp[coins.length-1 ][amount]!=Integer.MAX_VALUE?dp[coins.length-1 ][amount]:-1 ; }
空间优化
将上面的二维改成一维就是像下面一样，注意内层的循环！因为后面是 f[i][j-c]+1 所以需要依赖同一层前面的结果，所以必须顺序的遍历
public int coinChange (int [] coins,int amount) int [] dp=new int [amount+1 ]; Arrays.fill(dp,Integer.MAX_VALUE); dp[0 ]=0 ; for (int i=0 ;i<coins.length;i++) { for (int j=coins[i];j<=amount;j++) { if (dp[j-coins[i]]!=Integer.MAX_VALUE) { dp[j]=Math.min(dp[j-coins[i]]+1 ,dp[j]); } } } return dp[amount]==Integer.MAX_VALUE?-1 :dp[amount]; }
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个
示例 1:
输入: amount = 5 , coins = [1 , 2 , 5 ] 输出: 4 解释: 有四种方式可以凑成总金额: 5 =5 5 =2 +2 +1 5 =2 +1 +1 +1 5 =1 +1 +1 +1 +1
示例 2:
输入: amount = 3 , coins = [2 ] 输出: 0 解释: 只用面额2 的硬币不能凑成总金额3 。
示例 3:
输入: amount = 10 , coins = [10 ] 输出: 1
注意:
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
解法一
求方案数，不考虑顺序
public int change (int amount, int [] coins) if (coins==null || coins.length<=0 ) { return amount==0 ?1 :0 ; } int [][] dp=new int [coins.length][amount+1 ]; for (int i=0 ;i<coins.length;i++) { for (int j=0 ;j<=amount;j++) { if (i==0 ) { dp[0 ][j]=j%coins[i]==0 ?1 :0 ; }else if (j==0 ) { dp[i][0 ]=1 ; }else { dp[i][j]= j>=coins[i]?dp[i-1 ][j]+dp[i][j-coins[i]]:dp[i-1 ][j]; } } } return dp[coins.length-1 ][amount]; }
空间优化
f(5)=f(4)+f(3)+f(0) 突然感觉写二维的有点多余。。。这种子结构要清晰的多
public int change (int amount, int [] coins) int [] dp=new int [amount+1 ]; dp[0 ]=1 ; for (int i=0 ;i<coins.length;i++) { for (int j=0 ;j<=amount;j++) { dp[j]=j-coins[i]>=0 ?dp[j]+dp[j-coins[i]]:dp[j]; } } return dp[amount]; }
解法二
记忆化递归，基本上dp能过得，记忆化递归一定能过，相比之下，我觉得记忆化递归会好写一些
public int change (int amount, int [] coins) if (coins==null || coins.length<=0 ) { return amount==0 ?1 :0 ; } cache=new Integer[coins.length][amount+1 ]; return takeCoins(amount,coins,0 ); } Integer[][] cache=null ; public int takeCoins (int amount,int [] coins,int index) if (index>=coins.length || amount<0 ) { return 0 ; } if (cache[index][amount]!=null ) { return cache[index][amount]; } if (amount==0 ) { return 1 ; } return cache[index][amount]=takeCoins(amount-coins[index],coins,index)+takeCoins(amount,coins,index+1 ); }
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
解法一
和上面的一样的，但是这里有一些其他的方法，记录下，元素解法就不写了，和上面的一样
int mod=1000000007 ;public int waysToChange (int n) n/=5 ; int [] coins={5 ,2 ,1 }; long [] dp=new long [n+1 ]; Arrays.fill(dp,1L ); for (int i=0 ;i<coins.length;i++){ for (int j=coins[i];j<=n;j++){ dp[j]=(dp[j]+dp[j-coins[i]])%mod; } } return (int )(dp[n]%mod); }
直接把时间从114ms干到了17ms，其实时间复杂度没变，但是缩小了解空间，所以整体的时间会提高很多，当然这里能缩小的原因主要还是因为题目比较特殊
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1 , 2 , 3 ] target = 4 所有可能的组合为： (1 , 1 , 1 , 1 ) (1 , 1 , 2 ) (1 , 2 , 1 ) (1 , 3 ) (2 , 1 , 1 ) (2 , 2 ) (3 , 1 ) 请注意，顺序不同的序列被视作不同的组合。 因此输出为 7 。
进阶：
解法一
记忆化递归，没啥好说的
public int combinationSum4 (int [] nums, int target) if (nums==null || nums.length<=0 ) { return 0 ; } cache=new Integer[target+1 ]; return combination(nums,target); } Integer[] cache=null ; public int combination (int [] nums,int target) if (cache[target]!=null ) { return cache[target]; } if (target==0 ) { return 1 ; } int res=0 ; for (int i=0 ;i<nums.length;i++) { if (target-nums[i]>=0 ) { res+=combination(nums,target-nums[i]); } } return cache[target]=res; }
解法二
动态规划，乍一看好像和上面一题一样，实际上并不一样，这里是考虑顺序的，最优子结构也是
f(5)=f(4)+f(3)+f(0) 这样的
public int combinationSum4 (int [] nums,int target) int [] dp=new int [target+1 ]; dp[0 ]=1 ; for (int i=0 ;i<=target;i++) { for (int j=0 ;j<nums.length;j++) { dp[i]+= i>=nums[j]?dp[i-nums[j]]:0 ; } } return dp[target]; }
这里还是要存个疑啊，没搞明白啊，为啥交换个顺序就不一样了呢？一个是按行打表，一个是按列打表？？？还是递归好写。。。
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1 , 1 , 1 , 1 , 1 ], S: 3 输出: 5 解释: -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 一共有5 种方法让最终目标和为3 。
注意:
数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下
解法一
后面的题都优先写记忆化递归了，动态规划确实有点难顶
Integer[][] cache=null ; public int findTargetSumWays (int [] nums, int S) if (nums==null || nums.length<=0 || S>1000 ) { return 0 ; } int sum=0 ; for (int n:nums)sum+=n; if (S>sum)return 0 ; cache=new Integer[nums.length][2 *sum+1 ]; return findTarget(nums,S,0 ,2 *sum+1 ); } public int findTarget (int [] nums,int S,int index,int max) if (S==0 && index ==nums.length) { return 1 ; } if (index>=nums.length) { return 0 ; } if (S <0 && cache[index][S+max]!=null ){ return cache[index][S+max]; } if (S>=0 && cache[index][S]!=null ) { return cache[index][S]; } int temp=findTarget(nums,S-nums[index],index+1 ,max)+findTarget(nums,S+nums[index],index+1 ,max); if (S<0 ) { cache[index][S+max]=temp; }else { cache[index][S]=temp; } return temp; }
这题还是挺有意思的，因为里面是有负数的，直接记忆化是不行的，需要转换一下，这里我是直接将cache数组扩大，同时保证不会有覆盖，所以直接扩大为 2sum就ok，这样整个S的范围就从[-sum,+sum] 变为 [0,2sum] 从而可以缓存所有的递归结果，其实也可以使用两个数组一个存正数，一个存负数，然后只需要符号取反就ok了，只不过占用的空间会大一点
解法二
正儿八经的01背包做法
public int findTargetSumWays (int [] nums, int S) if (nums==null || nums.length<=0 ) return 0 ; int sum=0 ; for (int i=0 ;i<nums.length;i++) sum+=nums[i]; if ((sum+S)%2 !=0 || S>sum) return 0 ; int target=(sum+S)/2 ; int [] dp=new int [target+1 ]; dp[0 ]=1 ; for (int i=0 ;i<nums.length;i++){ for (int j=target;j>=nums[i];j--){ dp[j]+=dp[j-nums[i]]; } } return dp[target]; }
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头 ，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量 。如果没有石头剩下，就返回 0。
示例：
输入：[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 ]，这就是最优值。
提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
解法一
想了一下，其实就是在所有石头中选取部分石头，求这部分的石头和大于sum/2的最小值（和正常的背包思路反着来的）
Integer[][] dp=null ; public int lastStoneWeightII (int [] stones) int sum=0 ; for (int i=0 ;i<stones.length;i++) { sum+=stones[i]; } dp=new Integer[stones.length+1 ][sum]; return 2 *dfs(stones,0 ,0 ,sum)-sum; } public int dfs (int [] stones,int index,int psum,int sum) if (2 *psum>=sum){ return psum; } if (dp[index][psum]!=null ){ return dp[index][psum]; } int min=Integer.MAX_VALUE; for (int i=index;i<stones.length;i++) { min=Math.min(dfs(stones,i+1 ,psum+stones[i],sum),min); } return dp[index][psum]=min; }
当我按照这个思路i写出来后发现不好改递推了😂，这个思路确实有一点点怪
解法二
正常的01背包解法，其实把上面的结论反过来就行了，既然要求一个大于等于sum/2的最小值，其实就是求一个小于等于sum/2 的最大值，这样一说就很清楚了，经典的01背包
public int lastStoneWeightII (int [] stones) if (stones==null ||stones.length<=0 ){ return 0 ; } int n=stones.length; int sum=0 ; for (int i=0 ;i<n;i++){ sum+=stones[i]; } int amount=sum/2 ; int [] dp=new int [amount+1 ]; for (int i=0 ;i<stones.length;i++) { for (int j=amount;j>=stones[i];j--) { dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]); } } return sum-2 *dp[amount]; }
这里的retrun有两种写法，推荐第二种，第一种还要判奇偶
拿到这题的的第一个解法其实是贪心，每次消除两个最大的，用优先队列维护石头大小
天真的错误解法 74 / 82 个通过测试用例
这个思路其实是 这题的弱化版本 1046. 最后一块石头的重量 的解法
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:
输入: Array = {"10" , "0001" , "111001" , "1" , "0" }, m = 5 , n = 3 输出: 4 解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10" ,"0001" ,"1" ,"0" 。
示例 2:
输入: Array = {"10" , "0" , "1" }, m = 1 , n = 1 输出: 2 解释: 你可以拼出 "10" ，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
解法一
之前只用Java写了个记忆化的，补一下纯dp的
func findMaxForm (strs []string , m int , n int ) int var sn = len (strs) var dp = make ([][]int , m+1 ) var Max = func (a, b int ) int if a>b {return a};return b} for i := 0 ; i <= m; i++ { dp[i] = make ([]int , n+1 ) } for i := 0 ; i < sn; i++ { zero, one := count(strs[i]) for j := m; j >= zero; j-- { for k := n; k >= one; k-- { dp[j][k] = Max(dp[j][k], dp[j-zero][k-one]+1 ) } } } return dp[m][n] } func count (str string ) (int , int ) var one, zero = 0 , 0 for i := 0 ; i < len (str); i++ { if str[i] == '0' { zero++ } if str[i] == '1' { one++ } } return zero, one }
解法二
其实这是一个多重背包问题，一个物品有多个权值
Integer [][][] cache=null ; public int findMaxForm (String[] strs, int m, int n) cache=new Integer[m+1 ][n+1 ][strs.length]; return findMax(strs,m,n,0 ); } public int findMax (String[] strs, int m, int n,int index) if (index>=strs.length) { return 0 ; } if (cache[m][n][index]!=null ) { return cache[m][n][index]; } int [] oz=count(strs[index]); if (oz[1 ]<=n && oz[0 ]<=m) { return cache[m][n][index]=Math.max(1 +findMax(strs,m-oz[0 ],n-oz[1 ],index+1 ),findMax(strs,m,n,index+1 )); } return cache[m][n][index]=findMax(strs,m,n,index+1 ); } public int [] count(String str){ int one=0 ,zero=0 ; char [] s=str.toCharArray(); for (char c:s) { if (c=='1' ) { one++; }else { zero++; } } return new int []{zero,one}; }
你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。
请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。
单词拼写游戏的规则概述如下：
玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
单词表 words 中每个单词只能计分（使用）一次。
根据字母得分情况表score，字母 ‘a’, ‘b’, ‘c’, … , ‘z’ 对应的得分分别为 score[0], score[1], …, score[25]。
本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和
示例 1：
输入：words = ["dog" ,"cat" ,"dad" ,"good" ], letters = ["a" ,"a" ,"c" ,"d" ,"d" ,"d" ,"g" ,"o" ,"o" ], score = [1 ,0 ,9 ,5 ,0 ,0 ,3 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,2 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ] 输出：23 解释： 字母得分为 a=1 , c=9 , d=5 , g=3 , o=2 使用给定的字母表 letters，我们可以拼写单词 "dad" (5 +1 +5 )和 "good" (3 +2 +2 +5 )，得分为 23 。 而单词 "dad" 和 "dog" 只能得到 21 分。
示例 2：
输入：words = ["xxxz" ,"ax" ,"bx" ,"cx" ], letters = ["z" ,"a" ,"b" ,"c" ,"x" ,"x" ,"x" ], score = [4 ,4 ,4 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,5 ,0 ,10 ] 输出：27 解释： 字母得分为 a=4 , b=4 , c=4 , x=5 , z=10 使用给定的字母表 letters，我们可以组成单词 "ax" (4 +5 )， "bx" (4 +5 ) 和 "cx" (4 +5 ) ，总得分为 27 。 单词 "xxxz" 的得分仅为 25 。
示例 3：
输入：words = ["leetcode" ], letters = ["l" ,"e" ,"t" ,"c" ,"o" ,"d" ], score = [0 ,0 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ] 输出：0 解释： 字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。
提示：
1 <= words.length <= 141 <= words[i].length <= 151 <= letters.length <= 100letters[i].length == 1score.length == 260 <= score[i] <= 10words[i] 和 letters[i] 只包含小写的英文字母
解法一
看着题目就知道这题不简单😂，11.10的周赛最后一题，1ms，用01背包的思路做的，很多地方其实还没处理好
public int maxScoreWords (String[] words, char [] letters, int [] score) int [] les=new int [26 ]; for (int i=0 ;i<letters.length;i++) { les[letters[i]-'a' ]++; } return maxScoreWords(words,letters,score,0 ,les); } public int maxScoreWords (String[] words, char [] letters, int [] score,int index,int [] les) if (index==words.length) { return 0 ; } int res=maxScoreWords(words,letters,score,index+1 ,les); String word=words[index]; if (hasWord(les,word)) { int [] bak=new int [les.length]; System.arraycopy(les,0 ,bak,0 ,les.length); res=Math.max(res,getScore(bak,word,score)+maxScoreWords(words,letters,score,index+1 ,bak)); } return res; } public boolean hasWord (int [] les,String word) int [] bak=new int [les.length]; System.arraycopy(les,0 ,bak,0 ,les.length); int count=0 ; for (char c:word.toCharArray()){ if (bak[c-'a' ]!=0 ) { bak[c-'a' ]--; count++; } } return count==word.length(); } public int getScore (int [] les,String word,int [] score) int sc=0 ; for (char c:word.toCharArray()) { les[c-'a' ]--; sc+=score[c-'a' ]; } return sc; }
Problem Description
春节将至，小明要去超市购置年货，于是小明去了自己经常去的都尚超市。
刚到超市，小明就发现超市门口聚集一堆人。用白云女士的话说就是：“那家伙，那场面，真是人山人海，锣鼓喧天，鞭炮齐呤，红旗招展。那可真是相当的壮观啊！”。好奇的小明走过去，奋力挤过人群，发现超市门口贴了一张通知，内容如下
值此新春佳节来临之际，为了回馈广大顾客的支持和厚爱，特举行春节大酬宾、优惠大放送活动。凡是都尚会员都可用会员积分兑换商品，凡是都尚会员都可免费拿k件商品 ，凡是购物顾客均有好礼相送。满100元送bla bla bla bla，满200元送bla bla bla bla bla…blablabla….
还没看完通知，小明就高兴的要死，因为他就是都尚的会员啊。迫不及待的小明在超市逛了一圈发现超市里有n件他想要的商品 。小明顺便对这n件商品打了分，表示商品的实际价值。小明发现身上带了v1的人民币 ，会员卡里面有v2的积分 。他想知道他最多能买多大价值的商品。
由于小明想要的商品实在太多了，他算了半天头都疼了也没算出来，所以请你这位聪明的程序员来帮帮他吧。
Input
输入包含多组测试用例。 每组数据的第一行是四个整数n，v1，v2，k； 然后是n行，每行三个整数a，b，val，分别表示每个商品的价钱，兑换所需积分，实际价值。 [Technical Specification] 1 <= n <= 100 0 <= v1, v2 <= 100 0 <= k <= 5 0 <= a, b, val <= 100 Ps. 只要钱或者积分满足购买一件商品的要求，那么就可以买下这件商品。
Output
对于每组数据，输出能买的最大价值。 详细信息见Sample。
Sample Input
5 1 6 1 4 3 3 0 3 2 2 3 3 3 3 2 1 0 2 4 2 5 0 0 1 0 4 4 1 3 3 4 3 4 4
Sample Output
Source
解法一
三维费用的背包，但是和前面的474.一和零 还有点不一样，三个维度的费用是无关的，而1和0中1的个数和0的个数是相关的
代码使用了Petr的输入模板，自己改进了下，增加了输入结束判断，所以看起来特别长
import java.util.*;import java.io.*;import java.math.*; public class Solve_HDOJ_4501 public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); public static void main (String[] args) throws Exception InputReader in = new InputReader(System.in); while (!in.EOF()) { int n = in.nextInt(); int v1 = in.nextInt(); int v2 = in.nextInt(); int k = in.nextInt(); int [][] cost = new int [n][3 ]; for (int i = 0 ; i < n; i++) { cost[i][0 ] = in.nextInt(); cost[i][1 ] = in.nextInt(); cost[i][2 ] = in.nextInt(); } solve(n, v1, v2, k, cost); } out.flush(); out.close(); } public static void solve (int n, int v1, int v2, int k, int [][] cost) int [][][] dp = new int [k+1 ][v1+1 ][v2+1 ]; for (int i = 0 ; i < n; i++) { for (int j = k; j >= 0 ; j--) { for (int u = v1; u >= 0 ; u--) { for (int w = v2; w >= 0 ; w--) { int ans = 0 ; if (j >= 1 ) { ans = Math.max(ans, dp[j-1 ][u][w] + cost[i][2 ]); } if (u >= cost[i][0 ]) { ans = Math.max(ans, dp[j][u-cost[i][0 ]][w] + cost[i][2 ]); } if (w >= cost[i][1 ]) { ans = Math.max(ans, dp[j][u][w-cost[i][1 ]] + cost[i][2 ]); } dp[j][u][w] = Math.max(ans, dp[j][u][w]); } } } } out.println(dp[k][v1][v2]); } } class InputReader public BufferedReader reader; public StringTokenizer tokenizer; public InputReader (InputStream stream) reader = new BufferedReader(new InputStreamReader(stream), 32768 ); tokenizer = null ; } public String next () while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public boolean EOF () String str = null ; try { str = reader.readLine(); if (str == null ) { return true ; } tokenizer = new StringTokenizer(str); } catch (IOException e) { throw new RuntimeException(e); } return false ; } int nextInt () return Integer.parseInt(next()); } long nextLong () return Long.parseLong(next()); } double nextDouble () return Double.parseDouble(next()); } BigInteger nextBigInteger () { return new BigInteger(next()); } BigDecimal nextBigDecimal () { return new BigDecimal(next()); } }
