BackPack I
– different sizes same price, ask maximum solution with fixed bag size
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
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.
Note
You can not divide any item into small pieces.
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.
Solution 1: DP – O(nm) time and O(nm) memory
state: f[i][j] = “前i”个数，取出一些组成和为<=j的最大值
function: f[i][j] = f[i-1][j – a[i]] + a[i] //取a[i]的情况
o f[i-1][j] //不取a[i]的情况
两种情况取max
public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i][j] = backPack[i - 1][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i][j] = Math.max(backPack[i][j], backPack[i - 1][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i][j] > max) {
max = backPack[i][j];
}
}
}
return max;
}
Solution 2. O(mn) time O(n) space, 利用行数取模优化空间 rolling array
public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i % 2][j] = backPack[(i - 1) % 2][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i % 2][j] = Math.max(backPack[i % 2][j], backPack[(i - 1) % 2][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i % 2][j] > max) {
max = backPack[i % 2][j];
}
}
}
return max;
}
Solution 3: dp
f[i][j] = 前i个item能不能正好组成j
f[i][j] = f[i-1][j-a[i]] //取a[i]
f[i-1][j] //不取a[i]
两者取或
return max j which f[i][j] == true
public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
boolean[][] backPack = new boolean[A.length + 1][m + 1];
backPack[0][0] = true;
for (int i = 1; i <= A.length; i++) {
backPack[i][0] = true;
}
for (int j = 1; j <= m; j++) {
backPack[0][j] = false;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
backPack[i][j] = backPack[i - 1][j];
if (j >= A[i - 1]) {
backPack[i][j] |= backPack[i - 1][j - A[i - 1]];
}
if (backPack[i][j]) {
max = j;
}
}
}
return max;
}
BackPack II
– different size and price, ask for maximum value with fixed bag size
Solution 1. O(m*n) time, O(m*n) space
f[i][j]:maximum value with first i items in A with a m sized bag
f[i][j] = f[i-1][j – a[i]] + v[i] //取a[i]的情况
= f[i-1][j] //不取a[i]的情况
两者取max, return f[n][m]
public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i][j] = maxValue[i - 1][j];
if (j >= A[i - 1]) {
maxValue[i][j] = Math.max(maxValue[i][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length][m];
}
Solution 2: O(m*n) time, O(m) space
利用rolling array 进行优化
public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i % 2][j] = maxValue[(i - 1) % 2][j];
if (j >= A[i - 1]) {
maxValue[i % 2][j] = Math.max(maxValue[i % 2][j], maxValue[(i - 1) % 2][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length % 2][m];
}
