0-1背包问题 ?前提知识
框架：
int dp[][] = new int[n+1][m+1]; int dp[0][...] = 0; int dp[...][0] = 0; for i in [1...n] ????for j in [1...m] ????//取两种选择的最优解 ????dp[i][w]= max( ????????将重量a价值b的物品装进背包, ????????不将重量a价值b的物品装进背包) ????return [n][w]; ?
代码如下：
int knapsack(int W,int N,int[] wt,int[] val){
?? ?//定义dp数组，初始化 dp[2][3] = 3 表示可以承重为3的前2个东西选择性放进背包的最优解（最大价值）为3
?? ?int[][] dp = new int[N+1][W+1];
?? ?for（int i=1;i<N;i++）{
?? ??? ?for(int w=1;w<=W;w++){
?? ??? ??? ?if(w-wt[i-1]<0){
?? ??? ??? ??? ?dp[i][w] = dp[i-1][w];
?? ??? ??? ?}else{
?? ??? ??? ??? ?dp[i][w] = Math.max(
?? ??? ??? ??? ?dp[i-1][w-wt[i-1]]+val[i-1],
?? ??? ??? ??? ?dp[i-1][w]
?? ??? ??? ?);
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?)
?? ??? ?}
?? ?}
?? ?return dp[N][W];
}
Leetcode416：分割等和子集
-
题目：
-
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
-
-
思路：
-
将分割等和问题可以看成类似背包问题
-
如果数组的和为奇数，则不可能将其分割成等和子集
-
如果数组的和为偶数，则求数组的和的一半，将其一半看成背包问题，定义一个二维数组[i] [j]代表的含义，前i个数是否可以刚好恰好分成数组的和j的一半，则剩下的数自然成为另外的一半
-
-
代码如下：
class?Solution?{
? ?public?boolean?canPartition(int[]?nums) {
? ? ? ?int?n?=?nums.length;
? ? ? ?int?sum?=?0;
? ? ? ?for(int?i=0;i<n;i++){
? ? ? ? ? ?sum+=nums[i];
? ? ? }
? ? ? ?if(sum%2!=0){
? ? ? ? ? ?return?false;
? ? ? }
? ? ? ?sum?=?sum/2;
? ? ? ?boolean[][]?dp?=?new?boolean[n+1][sum+1];
? ? ? ?for(int?i?=?0;i<=?n;i++){
? ? ? ? ? ?dp[i][0]?=?true;
? ? ? }
?
? ? ? ?for(int?i?=1;i<=n;i++){
? ? ? ? ? ?for(int?j?=1;j<=sum;j++){
? ? ? ? ? ? ? ?if(j-nums[i-1]<0){
? ? ? ? ? ? ? ? ? ?dp[i][j]?=?dp[i-1][j];
? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ?dp[i][j]?=?dp[i-1][j]?||?dp[i-1][j-nums[i-1]];
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
? ? ? ?return?dp[n][sum];
? }
}
Leetcode518:零钱兑换II
-
题目：
-
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
-
-
思路：
-
背包问题：定义二维数组dp；dp[i] [j] 代表 记录前i种硬币可以组合成j金额的组合数；
-
没加入一种新的硬币，有如下两种情况
-
1.所收集的总金额小于硬币金额，则选择不把新的硬币加入，返回使用i-1种硬币组合成j金额的组合数
-
2.所收集的总金额大于硬币金额，则选择把新的硬币加入，则返回使用i-1种硬币组合成j金额的组合数 与 使用i种硬币组合成（j金额-硬币金额）的组合数之和
-
-
-
代码如下：
class?Solution?{
? ?public?int?change(int?amount,?int[]?coins) {
? ? ? ?int?n?=?coins.length;
? ? ? ?int[][]?dp?=?new?int[n+1][amount+1];
? ? ? ?for(int?i?=?0;i<=?n;i++){
? ? ? ? ? ?dp[i][0]?=?1;
? ? ? }
? ? ? ?for(int?i?=1;i<=n;i++){
? ? ? ? ? ?for(int?j?=1;j<=amount;j++){
? ? ? ? ? ? ? ?if(j-coins[i-1]<0){
? ? ? ? ? ? ? ? ? ?dp[i][j]?=?dp[i-1][j];
? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ?dp[i][j]?=?dp[i-1][j]+dp[i][j-coins[i-1]];
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
? ? ? ?return?dp[n][amount];
? }
}
