https://zhengyang2015.gitbooks.io/lintcode/backpack_i_92.html
用子问题定义状态：即f[i][v]表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值。则其状态转移方程便是： f[i][j] = max{f[i-1][j], j>=A[i-1]? f[i-1][j-A[i-1]]+V[i-1] : 0}
O(nm)
http://www.cnblogs.com/EdwardLiu/p/4269149.html
1D code:
https://zhengyang2015.gitbooks.io/lintcode/backpack_iii_440.html
https://zhengyang2015.gitbooks.io/lintcode/backpack_iv_562.html
Backpack V 563
https://zhengyang2015.gitbooks.io/lintcode/backpack_v_563.html
https://zhengyang2015.gitbooks.io/lintcode/backpack_vi_564.html
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
Notice
You can not divide any item into small pieces.
Example
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.
You function should return the max size we can fill in the given backpack.
Challenge
O(n x m) time and O(m) memory.
O(n x m) memory is also acceptable if you do not know how to optimize memory.
https://www.cnblogs.com/lz87/p/6928227.html
for j, we can also from m to 1
基础背包类问题，用DP解。两种方法本质都一样，只是表述不同。
State: T[i][j]: the max size we can get out of the first i items when the backpack size is j.
Function: T[i][j] = Math.max(T[i - 1][j], T[i - 1][j - A[i - 1]] + A[i - 1]), if j >= A[i - 1];
T[i][j] = T[i - 1][j], if j < A[i - 1].
Initialization: T[i][0] = T[0][j] = 0
Answer: T[A.length][m]
public int backPack(int m, int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int[][] T = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
T[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
T[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
if (j >= A[i - 1]) {
T[i][j] = Math.max(T[i - 1][j], T[i - 1][j - A[i - 1]] + A[i - 1]);
} else {
T[i][j] = T[i - 1][j];
}
}
}
return T[A.length][m];
}
public int backPack(int m, int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int[][] T = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
T[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
T[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = m; j >= m; j--) {
if (j >= A[i - 1]) {
T[i][j] = Math.max(T[i - 1][j], T[i - 1][j - A[i - 1]] + A[i - 1]);
} else {
T[i][j] = T[i - 1][j];
}
}
}
return T[A.length][m];
}
-- should change the order m, n基础背包类问题，用DP解。两种方法本质都一样，只是表述不同。
第一种方法为dp[i][j]表示i容量的背包在j件物品中能取的最大值。分两种情况：一种情况为不要第j件物品，则最优情况为背包容量为i时前j－1件物品的最优值；第二种情况为要第j件物品，则最优情况为背包容量为i-第j件物品体积时前j－1件物品的最优值加上第j件物品的值，这种情况要求i-第j件物品体积 >= 0。取两种情况里面较大的作为dp[i][j]的值。
public int backPack(int m, int[] A) {
if(m == 0 || A == null || A.length == 0){
return 0;
}
int n = A.length;
int[][] fillPack = new int[m + 1][n + 1];
for(int i = 0; i <= m; i++){
fillPack[i][0] = 0;
}
for(int j = 0; j <= n; j++){
fillPack[0][j] = 0;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(i - A[j - 1] >= 0){
//第二种情况为要第j件物品，则最优情况为背包容量为i-第j件物品体积时前j－1件物品的最优值加上第j件物品的值。
fillPack[i][j] = Math.max(fillPack[i][j - 1], fillPack[i - A[j - 1]][j - 1] + A[j - 1]);
}else{//一种情况为不要第j件物品，则最优情况为背包容量为i时前j－1件物品的最优值；
fillPack[i][j] = fillPack[i][j - 1];
}
}
}
return fillPack[m][n];
} public int backPack(int m, int[] A) {
boolean f[][] = new boolean[A.length + 1][m + 1];
f[0][0] = true;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j <= m; j++) {
f[i + 1][j] = f[i][j];
if (j >= A[i] && f[i][j - A[i]]) {
f[i + 1][j] = true;
}
} // for j
} // for i
for (int i = m; i >= 0; i--) {
if (f[A.length][i]) {
return i;
}
}
return 0;
}
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?
Notice
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.
Challenge
O(n x m) memory is acceptable, can you do it in O(m) memory?
和I类似。 value[i][j]表示容量为i的背包在前j件物品中能取的最大价值。分两种情况考虑：不要第j件物品，则value[i][j] = value[i][j-1]；要第j件物品，则value[i][j]=value[i－A［j］][j-1]+V[j]，这种情况要求i-A[j]>=0。取两种情况里面较大的作为value[i][j]的值。这种方法空间复杂度为O(n * m)。
public int backPackII(int m, int[] A, int V[]) {
if(m == 0 || A == null || A.length == 0){
return 0;
}
int n = A.length;
int[][] value = new int[m + 1][n + 1];
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(i -A[j - 1] >= 0){
value[i][j] = Math.max(value[i][j - 1], value[i - A[j - 1]][j - 1] + V[j - 1]);
}else{
value[i][j] = value[i][j - 1];
}
}
}
return value[m][n];
}
第二种方法可以将空间复杂度优化到O(m)。f[j]表示背包容量为j时在前i件物品中能够选取的最大价值。到第i件物品时，考虑第i件物品装还是不装。背包容量j从最大的容量m开始依次递减遍历，只考虑更新背包容量大于A[i]的情况，即加上V[i]之后是否结果会更优，背包容量小于A[i]的情况不用考虑因为第i件物品根本装不进此时容量的背包。若结果更优，则更新此时的f[j]（即装第i件物品时情况更优），否则不变（即不装第i件物品时情况更优）。因为f会记录i之前所有的最优情况，因此只需要m空间即可。物品从0遍历到n－1，即可求出前n件物品的最优值。
space O(m)：
public int backPackII(int m, int[] A, int V[]) {
int[] f = new int[m + 1];
for(int i = 0; i < n; i++){
for(int j = m; j >= A[i]; j--){//\\
if(f[j] < f[j - A[i]] + V[i]){
f[j] = f[j - A[i]] + V[i];
}
}
}
return f[m];
}
其实第二种方法相当于使用滚动数组。因为状态函数为
value[i][j]=max(value[i－A［j］][j-1]+V[j], value[i][j-1])
可以看出只和j－1有关，因此保存两行信息就足够了。使用滚动数组必须逐行填写，因为在计算下一行的时候需要上一行的信息，像第一种方法中那样逐列填写就不行。
public int backPackII(int m, int[] A, int V[]) {
if(m == 0 || A == null || A.length == 0){
return 0;
}
int n = A.length;
int[][] value = new int[m + 1][2];
for(int j = 1; j <= n; j++){
for(int i = 1; i <= m; i++){
if(i -A[j - 1] >= 0){
value[i][j % 2] = Math.max(value[i][(j - 1) % 2], value[i - A[j - 1]][(j - 1) % 2] + V[j - 1]);
}else{
value[i][j % 2] = value[i][(j - 1) % 2];
}
}
}
}用子问题定义状态：即f[i][v]表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值。则其状态转移方程便是： f[i][j] = max{f[i-1][j], j>=A[i-1]? f[i-1][j-A[i-1]]+V[i-1] : 0}
public int backPackII(int m, int[] A, int V[]) { 8 int[][] res = new int[A.length+1][m+1]; 9 res[0][0] = 0; 10 for (int i=1; i<=A.length; i++) { 11 for (int j=0; j<=m; j++) { 12 if (j - A[i-1] < 0) 13 res[i][j] = res[i-1][j]; 14 if (j - A[i-1] >= 0) { 15 res[i][j] = Math.max(res[i-1][j], res[i-1][j-A[i-1]]+V[i-1]); 16 } 17 } 18 } 20 return res[A.length][m]; 21 }
Use one dimension array:
public int backPackII(int m, int[] A, int V[]) {
int[] d = new int[m+1];
for (int i = 1; i <= A.length; i++) {
for (int j = m; j >= 0; j--) {
if (j == 0) {
d[j] = 0;
} else {
if (A[i-1] <= j) {
d[j] = Math.max(d[j-A[i-1]]+V[i-1], d[j]);
}
}
}
}
return d[m];
}
O(nm)
Given n items with size A[i], an integer m denotes the size of a backpack.
How full you can fill this backpack? Note You can not divide any item into small pieces.
2D code:
7 public int backPack(int m, int[] A) { 8 // write your code here 9 boolean[][] res = new boolean[A.length+1][m+1]; 10 res[0][0] = true; 11 for (int i=1; i<=A.length; i++) { 12 for (int j=0; j<=m; j++) { 13 res[i][j] = res[i-1][j] || (j-A[i-1]>=0 && res[i-1][j-A[i-1]]); 14 } 15 } 16 for (int j=m; j>=0; j--) { 17 if (res[A.length][j]) return j; 18 } 19 return 0; 20 }
7 public int backPack(int m, int[] A) { 8 if (A.length==0) return 0; 9 10 int len = A.length; 11 boolean[] size = new boolean[m+1]; 12 Arrays.fill(size,false); 13 size[0] = true; 14 for (int i=1;i<=len;i++) 15 for (int j=m;j>=0;j--){ 16 if (j-A[i-1]>=0 && size[j-A[i-1]]) 17 size[j] = size[j-A[i-1]]; 18 } 19 20 for (int i=m; i>=0;i--) 21 if (size[i]) return i; 22 23 return 0; 24 }Backpack III 440
https://zhengyang2015.gitbooks.io/lintcode/backpack_iii_440.html
Given n kind of items with size Ai and value Vi( each item has an infinite number available) and a backpack with size m. What's the maximum value can you put into the backpack?
Notice
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 15.
这道题和II的思想一样，f[j]表示容量为j的背包对前i件物品能取的最大值，其中物品可以重复选取。对物品从0遍历到n－1，每次只有比A[i]大的背包容量才有可能被更新。
和II不同的是，这道题物品可以重复选择，所以内层遍历j的时候从小到大遍历，这样物品可以重复选取。比如一开始在j的时候取了i，然后随着j的增大，在j'的时候又取了i，而恰好j = j' - A[i]，在这种情况下i就被重复选取。如果从大往小遍历则所有物品只能取一次，所以II中是从大往小遍历。
因此可以重复取元素则背包容量从小到大遍历，反之从大到小遍历。
public int backPackIII(int[] A, int[] V, int m) {
// Write your code here
int[] f = new int[m + 1];
for(int i = 0; i < A.length; i++){
for(int j = A[i]; j <= m; j++){
//对于当前物品i，若j从小到大的话，很可能在j之前的j-A[i]时已经放过第i件物品了，在j时再放就是重复放入；若j从大到小，则j之前的所有情况都没有更新过，不可能放过第i件物品，所以不会重复放入。
if(f[j - A[i]] + V[i] > f[j]){
f[j] = f[j - A[i]] + V[i];
}
}
}
return f[m];
}https://zhengyang2015.gitbooks.io/lintcode/backpack_iv_562.html
Given n items with size nums[i] which an integer array and all positive numbers, no duplicates. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.
Each item may be chosen unlimited number of times.
Example
Given candidate items [2,3,6,7] and target 7,
A solution set is:
[7]
[2, 2, 3]
return 2
这道题思路和III几乎一样，dp[j]表示背包容量为j时，对前i中物品来说能填满背包的方法数。当前元素为i时，背包容量大于等于nums[i]的才有可能被更新。此时，对于j容量的背包，其新的方法数为前i－1件物品能装满j容量背包的方法数（即不装第i件物品的方法数）＋前i-1件物品能装满j-nums[i]容量的背包的方法数（即装第i件物品的方法数）。这里状态方程只是把III中的max改成了+。所有求总共有多少种方法的题都可以从最大值问题变换max为+得到。因此，状态函数为：
dp[j] = dp[j] + dp[j - nums[i]] (右边的dp[j]表示上一行中（即i－1件物品）能装满j容量的方法数)
public int backPackIV(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 0; i < nums.length; i++){
for(int j = nums[i]; j <= target; j++){
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}https://zhengyang2015.gitbooks.io/lintcode/backpack_v_563.html
Given n items with size nums[i] which an integer array and all positive numbers. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.
Each item may only be used once.
Example
Given candidate items [1,2,3,3,7] and target 7,
A solution set is:
[7]
[1, 3, 3]
return 2
这题和IV几乎一样, 不同的是元素只能取一次，因此内层遍历j的时候从大到小遍历（解释见III）。dp[j]表示背包容量为j时，对前i件物品且每件物品只能取一次的情况下能取的最大值。dp[0]解释一下：就是将容量为0的背包装满的方法，显然只有一种，就是什么都不装
public int backPackV(int[] nums, int target) {
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];
}https://zhengyang2015.gitbooks.io/lintcode/backpack_vi_564.html
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.
Notice
The different sequences are counted as different combinations.
Example
Given nums = [1, 2, 4], target = 4
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
return 6
dp[j]表示背包容量为j时，数组nums能装满j的方法数量。
可以想到的方法是对于当前背包容量j，假设最后加入的元素为当前遍历的元素i，则将i元素最后加入的方法数量为dp[j - nums[i]]（此时要求j - nums[i] >= 0），将数组元素全部遍历当过i为止。其中，初始化dp[0]=1，表示数组元素将容量为0的背包装满的方法数为1（即什么元素都不取这一种方法）。
这道题并不难，但需要注意要和IV，V的区别。IV，V中的方法和元素位置有关系，元素的相对位置不能变化，不能先取后面的元素再取前面的元素，即相同元素组成的方法被视为一种方法（就算排列不同），其dp[j]的含义为前i件物品装满容量j的方法数，因此只和i之前的物品相关，而和i之后的物品无关。这道题则说明不同的顺序被认为是不同的方法，因此和元素位置无关，可以先取后面的元素再取前面的元素，即相同元素的不同排列被视为不同的方法，其dp[j]表示的是数组nums装满容量j的方法数，是和数组中所有元素有关。
之前几题能够用一维dp表示的本质其实是因为当前行的值只和上一行有关，因此用动态数组两行就行，如果直接在上一行更新当前行的状态则只需要一行即可，因此其本质就是还是二维dp。但是这道题真的是一维dp，即当前容量的填装数量只和之前容量填装的结果有关，只不过每次填装都要遍历整个nums数组来寻找相关的之前容量的状态，因此要用两重for循环。
public int backPackVI(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 1; i <= target; i++){
for(int j = 0; j < nums.length; j++){
if(i - nums[j] >= 0){
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}