今天花了一天时间把背包问题的主题做了一轮
背包问题I
思路就是dp[i][j] 代表j 重量时候能前i个包能装的最大量
if(j-A[i-1]<0)
dp[i][j] = dp[i-1][j] 没有第i个包的空间
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + A[i-1]) 这表示第i个包可以放进去
得到最大的dp[i][j]
其实可以通过滚动数组降维，这里我就不提了
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
int dp[][] = new int[A.length +1][m+1];
for(int i = 1; i <= A.length; i++){
for(int j = 0; j <= m; j++){
if(j-A[i-1] < 0){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] +A[i-1]);
}
}
}
return dp[A.length][m];
}
}
背包问题II
思路类似I
dp[i][j] 代表前i个物品装在j容量的最大价值
if(j-A[i-1]<0)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]]+V[i-1])
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
// write your code here
int[][] dp = new int[A.length + 1][m+1];
for(int i = 1; i <= A.length; i++){
for(int j = 0; j <= m; j++){
if(j < A[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i - 1][j - A[i-1]] + V[i-1]);
}
}
}
return dp[A.length][m];
}
}
背包问题III
背包问题III
这个有些tricky，
同样设置dp[i][j] 代表取前i个物品装在j容量包里的最大价值
但是这里i物品的取用是无限的
下面是状态方程
if(j-A[i-1]<0)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = max(dp[i-1][j], dp[i][j-A[i-1]]+V[i-1])
这里和背包问题II不同，其实就是两种情况，一种是第i个物品不取，另一种是第i个物品至少取一件
public class Solution {
/**
* @param A: an integer array
* @param V: an integer array
* @param m: An integer
* @return: an array
*/
public int backPackIII(int[] A, int[] V, int m) {
// write your code here
int dp[][] = new int[A.length + 1][m + 1];
for(int i = 1; i <= A.length; i++){
for(int j = 0; j <= m; j++){
if(j < A[i - 1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i][j - A[i-1]] + V[i-1]);
}
}
}
return dp[A.length][m];
}
}
背包问题IV
背包问题IV
这里的dp[i][j] 是前i 个物品装在j容量的背包里的组合数
if(j-nums[i-1]<0)
dp[i][j] = dp[i-1][j]
如果第i个物品放不进去，那么dp[i][j] = dp[i-1][j]
else
如果放的进去，就是前i-1 在j容积下的组合数加上前i 在j-nums[i-1]容积下的组合数
dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]]
public class Solution {
/**
* @param nums: an integer array and all positive numbers, no duplicates
* @param target: An integer
* @return: An integer
*/
public int backPackIV(int[] A, int target) {
// write your code here
int dp[][] = new int[A.length + 1][target + 1];
dp[0][0] = 1;
for(int i = 1; i <= A.length; i++){
for(int j = 0; j <= target; j++){
if(j - A[i-1] < 0){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-A[i-1]];
}
}
}
return dp[A.length][target];
}
}
背包问题V
dp[i][j] 为前i 个数填满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]]
public class Solution {
/**
* @param nums: an integer array and all positive numbers
* @param target: An integer
* @return: An integer
*/
public int backPackV(int[] nums, int target) {
// write your code here
int dp[][] = new int[nums.length + 1][target + 1];
dp[0][0] = 1;
for(int i = 1; i< nums.length + 1; i++){
for(int j = 0; j < target + 1; 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[nums.length][target];
}
}
背包问题VI
背包问题VI
这题无限次取用，且要的是不同的排列数
dp[j] 代表j 重量可以装载的最大组合数
这轮的循环要先遍历重量，再遍历物品，因为每前i物品的组合数都是累加上一个情况的组合数，因此要得到之前的最终dp[j]
if(j - nums[i] >= 0)
dp[j] += dp[j-nums[i-1]]
public class Solution {
/**
* @param nums: an integer array and all positive numbers, no duplicates
* @param target: An integer
* @return: An integer
*/
public int backPackVI(int[] nums, int target) {
//write your code here
int dp[] = new int[target+1];
dp[0] = 1;
for(int j = 0; j <= target; j++){
for(int i = 1; i <=nums.length; i++){
if(j-nums[i-1]>=0)
dp[j] += dp[j-nums[i-1]];
}
}
return dp[target];
}
}
网友评论