题目：backpack I （每个物品取一次，求最多能装多少物品）
Given n items with size Ai, an integer m denotes the size of a backpack. How full can you fill this backpack?
Input:
- 物品的大小:: int[]
- 背包的大小 ::int
Output:
- 背包最多能装多少:: int
Intuition:
典型的DP问题，dp array存档背包大小为j时，dp[i]表示在装或者不装第 i - 1号物品时最多能装多少物品。
- 不装第 i 号的物品: dp[i - 1][j]
- 装第 i 号物品： dp[i - 1][j - A[i - 1]] + A[i - 1]
举个例子: 物品大小[3, 4, 8, 5], 背包size为10
那么在每次装一个物品时，dp array的更新如下:
Array List: 0 0 0 3 3 3 3 3 3 3 3
Array List: 0 0 0 3 4 4 4 7 7 7 7
Array List: 0 0 0 3 4 4 4 7 8 8 8
Array List: 0 0 0 3 4 5 5 7 8 9 9
Code:
TC: (nm) SC: (nm)
public int backPack(int m, int[] A) {
// write your code here
if (A == null || A.length == 0){
return 0;
}
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] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[A.length][m];
}
当然，遇到二维数组的时候我们会考虑是不是要进行空间压缩，使用一维数组。
TC: (nm) SC: (m)
Code:
public int backPack(int m, int[] A) {
// write your code here
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 >= A[i]) {
dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
}
}
}
return dp[m];
}
题目：backpack II （每个物品取一次，求最多能装物品的最大价值）
Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?
Input:
- 物品的大小:: int[]
- 物品的价值:: int[]
- 背包的大小 ::int
Output:
- 背包能装物品的最大价值:: int
Intuition:
基本思想和backpack I是一样的，不同之处就在于我们更新的是物品的价值而不是物品的大小。
- 不装第 i 号的物品: dp[i - 1][j]
- 装第 i 号物品： dp[i - 1][j - A[i - 1]] + V[i - 1]
例子: 物品大小[2, 3, 5, 7], 物品价值[1, 5, 2, 4]，背包size为10
那么在每次装一个物品时，dp array的更新如下:
Array List: 0 0 1 1 1 1 1 1 1 1 1
Array List: 0 0 1 5 5 6 6 6 6 6 6
Array List: 0 0 1 5 5 6 6 6 7 7 8
Array List: 0 0 1 5 5 6 6 6 7 7 9
Code:
TC: (nm) SC: (nm)
public int backPack(int m, int[] A) {
// write your code here
if (A == null || A.length == 0){
return 0;
}
int[][] dp = new int[A.length + 1][m + 1];
for (int i = 1; i <=A.length; i++){
for (int j = m; j >= 0; j--){
if (j >= A[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[A.length][m];
}
同样的可以压缩空间
Code:
TC: (nm) SC: (m)
public int backPackII(int m, int[] A, int[] V) {
// write your code here
// write your code here
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 >= A[i]) {
dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
}
}
}
return dp[m];
}
题目：backpack III （每个物品可取无限次，求最多能装物品的最大价值）
Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?
Input:
- 物品的大小:: int[]
- 物品的价值:: int[]
- 背包的大小 ::int
Output:
- 背包能装物品的最大价值:: int
Intuition:
更新dp array值的策略是一样的。不过这次更新的顺序不再是从后到前，而是反过来了。这样在后半部的更新可以利用之前的值。
例子: 物品大小[2, 3, 5, 7], 物品价值[1, 5, 2, 4]，背包size为10
那么dp array的更新如下:
Array List: 0 0 1 1 2 2 3 3 4 4 5
Array List: 0 0 1 5 5 6 10 10 11 15 15
Array List: 0 0 1 5 5 6 10 10 11 15 15
Array List: 0 0 1 5 5 6 10 10 11 15 15
Code:
TC: O(nm) SC: O(m)
public int backPackIII(int[] A, int[] V, int m) {
// write your code here
// write your code here
// write your code here
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 = 0; j <= m; j++){
if (j >= A[i]) {
dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
}
}
}
return dp[m];
}
题目：backpack IV （每个物品可取无限次，从中找出所有的和为 target 的组合个数）
Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Input:
- 物品的大小:: int[]
- 目标值 ::int
Output:
- 所有的和为目标的组合个数:: int
Intuition:
用一个dp array存0到target的可能组合数，dp[i]的组合数可以根据之前组合数求得。 dp[i] += dp[i - num[i]] 或者 dp[i + num[i]] += dp[i]
Code:
TC: O(n*m) SC: O(m)
public int backPackIV(int[] nums, int target) {
// write your code here
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[target + 1];
dp[0] = 1;
for(int n: nums){
for(int i = 0; i <= target; i++){
if(n + i <= target){
dp[i + n] += dp[i] ;
}
}
}
return dp[target];
}
题目：backpack V （每个物品可取一次，从中找出所有的和为 target 的组合个数）
Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Input:
- 物品的大小:: int[]
- 目标值 ::int
Output:
- 所有的和为目标的组合个数:: int
Intuition:
与上一题不同，单次选择的话更新dp array的顺序应该从后到前。
Code:
TC: O(mn) SC: O(m)
public int backPackV(int[] nums, int target) {
// write your code here
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[target + 1];
dp[0] = 1;
for(int n: nums){
for(int i = target; i >= 0; i--){
if(n + i <= target){
dp[i + n] += dp[i] ;
}
}
}
return dp[target];
}
题目：backpack VI （每个物品可取无限次，数的顺序不同则会被认为是不同的组合,从中找出所有的和为 target 的组合个数）
Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Input:
- 物品的大小:: int[]
- 目标值 ::int
Output:
- 所有的和为目标的组合个数:: int
Intuition:
这个题与backpackIV 不同的一点就是同样的数，用在组合不同的位置可认为是有效的解。那么可以理解成，我们在每个size装物品的时候需要每个物品都试一遍，那么对物品size的循环就应该成为内循环了。
Code:
TC:O(mn) SC: O(m)
public int backPackVI(int[] nums, int target) {
// write your code here
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 0; i <= target; i++){
for(int n: nums){
if(n + i <= target){
dp[i + n] += dp[i];
}
}
printArrayList(dp);
}
return dp[target];
}
