Backpack
1. 0 / 1 back pack problem.
Given N non-negative integers and a target, Can we pick up any numbers from the N integers and its sum equals to the target. Return true of false
Note that target could equal to 0.
2. Lintcode: 0/1 Back pack II
Understand the problem:
It is another 0/1 back pack problem. The crux of the problem is to pick up the item from the array of which the sum is cloest to the target value.
So it is another DP problem, and we could define the DP functions.
1. 0 / 1 back pack problem.
Given N non-negative integers and a target, Can we pick up any numbers from the N integers and its sum equals to the target. Return true of false
- f[n + 1][Target]
- f[i][S] Given First i numbers, can we pick up some numbers and their sums equal to S
- Transit function: f[i][S] = f[i - 1][S- a[i]] (picked A[i])or f[i - 1][S] (not picked A[i])
- Initial state: f[0][0] = true; f[0][1 ... SUM] = false;
- Final state: f[n][target] .
Code (Java):
public class Solution {
public boolean backpack(int[] A, int target) {
if (A == null || A.length == 0 || target < 0) {
return false;
}
boolean[][] dp = new boolean[A.length + 1][target + 1];
dp[0][0] = true;
for (int i = 1; i <= A.length; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (j - A[i - 1] >= 0) {
dp[i][j] = dp[i][j] || dp[i - 1][j - A[i - 1]];
}
}
}
return dp[A.length][target];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] A = new int[]{2,3,5,7};
int target = 17;
System.out.println(sol.backpack(A, target));
}
}
2. Lintcode: 0/1 Back pack II
13%
Accepted
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.
Example
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 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.
It is another 0/1 back pack problem. The crux of the problem is to pick up the item from the array of which the sum is cloest to the target value.
So it is another DP problem, and we could define the DP functions.
- dp[A.length() + 1][m + 1], where dp[i][j] means the sum that pick some from first i items of which the sum are cloest to j.
- Initial state: all 0s, so no need to initialize.
- Transit function: dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i]] + A[i]);
- Final state: dp[A.length()][m].
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
*/
public int backPack(int m, ArrayList<integer> A) {
// write your code here
if (A == null || A.size() == 0 || m < 0) {
return 0;
}
int[][] dp = new int[A.size() + 1][m + 1];
// initialization
// no needed since all 0s
for (int i = 1; i <= A.size(); i++) {
for (int j = 0; j <= m; j++) {
int noPick = dp[i - 1][j];
int pick = 0;
if (j - A.get(i - 1) >= 0) {
pick = dp[i - 1][j - A.get(i - 1)] + A.get(i - 1);
}
dp[i][j] = Math.max(pick, noPick);
}
}
return dp[A.size()][m];
}
}
Follow-up: How about we want to find a solution?
The idea is to use back track from the end, each time we choose the optimal solution until we reached the beginning.
Code (Java):
import java.util.*;
public class Solution {
public List<Integer> backPack(int[] A, int target) {
List<Integer> result = new ArrayList<Integer>();
if (A == null || A.length == 0 || target <= 0) {
return result;
}
int[][] dp = new int[A.length + 1][target + 1];
for (int i = 1; i <= A.length; i++) {
for (int j = 0; j <= target; j++) {
int noChoose = dp[i - 1][j];
int choose = 0;
if (A[i - 1] <= j) {
choose = dp[i - 1][j - A[i - 1]] + A[i - 1];
}
dp[i][j] = Math.max(choose, noChoose);
}
}
findSolution(dp, A, result, A.length, target);
return result;
}
private void findSolution(int[][] dp, int[] A, List<Integer>
result, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (j - A[i - 1] >= 0 && (dp[i - 1][j - A[i - 1]] + A[i - 1] >
dp[i - 1][j])) {
result.add(A[i - 1]);
findSolution(dp, A, result, i - 1, j - A[i - 1]);
} else {
findSolution(dp, A, result, i - 1, j);
}
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] A = new int[]{2,3,5,7};
int target = 11;
List<Integer> result = sol.backPack(A, target);
for (Integer elem : result) {
System.out.print(elem + " ");
}
System.out.println();
}
}
A 1D space DP solution:
Note that for back pack solution, the DP only relies on dp[i - 1], so we may reduce the space cost by using a 1D array.
Code (Java):
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
*/
public int backPack(int m, ArrayList<Integer> A) {
// write your code here
if (A == null || A.size() == 0 || m < 0) {
return 0;
}
//int[][] dp = new int[A.size() + 1][m + 1];
int[] dp = new int[m + 1];
// initialization
// no needed since all 0s
for (int i = 0; i < A.size(); i++) {
//dp[0] = 0;
for (int j = m; j >= 0; j--) {
//int noPick = dp[i - 1][j];
int noPick = dp[j];
int pick = 0;
if (j - A.get(i) >= 0) {
//pick = dp[i - 1][j - A.get(i - 1)] + A.get(i - 1);
pick = dp[j - A.get(i)] + A.get(i);
}
//dp[i][j] = Math.max(pick, noPick);
dp[j] = Math.max(pick, noPick);
}
}
return dp[m];
}
}
Noted that the inner loop should start from the end in backward order. That is because we the result on dp[j] depends on dp[i - 1][j - A[i]]. So if we update the dp[j] from left to right, the previous results will be overwritten.
3. A general 0/1 back pack problem:
http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W.
Understand the problem:
The problem has two conditions to satisfy:
1. Pick up the some items from the array, such that 1. the sum of the value could reach the maximum, and 2. its weight should be less than the capacity W.
So we can solve the dp problem by defining the following:
- dp[n + 1][W + 1], where dp[i][j] means from the first i items we choose some, and its weight sum is less than the j, as well as the value sum is maximal.
- Initial state: 0.
- Transit function: There should have two cases.
- If wt[i] > j, we could not choose this item since it is over-weighted. In this case, dp[i][j] = dp[i - 1][j];
- Else, dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - wt[i]] + val[i]);
- Final state: return dp[n][W]
Code (Java):
public class Solution {
public int knapSack(int W, int[] val, int[] wt) {
if (val == null || val.length == 0 || wt == null || wt.length == 0 || W <= 0) {
return 0;
}
int[][] dp = new int[val.length + 1][W + 1];
for (int i = 1; i <= val.length; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j]; // no pickup
if (wt[i - 1] <= j) {
dp[i][j] = Math.max(dp[i][j],
dp[i - 1][j - wt[i - 1]] + val[i - 1]);
}
}
}
return dp[val.length][W];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] val = new int[]{60, 100, 120};
int[] wt = new int[]{10, 20, 30};
int W = 50;
System.out.println(sol.knapSack(W, val, wt));
}
}
public class Solution {
public int knapSack(int W, int[] val, int[] wt) {
if (val == null || val.length == 0 || wt == null || wt.length == 0 || W <= 0) {
return 0;
}
int[] dp = new int[W + 1];
for (int i = 1; i <= val.length; i++) {
for (int j = W; j >= 0; j--) {
if (wt[i - 1] <= j) {
dp[j] = Math.max(dp[j], dp[j - wt[i - 1]] + val[i - 1]);
}
}
}
return dp[W];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] val = new int[]{60, 100, 120};
int[] wt = new int[]{10, 20, 30};
int W = 50;
System.out.println(sol.knapSack(W, val, wt));
}
}
4. A multiple DP problem -- Each item can be picked up by k times.
In this question, each element could be selected at most n[i] times. Find the maximum value with the sum of the weight less or equal to W.
Again, the definition of the DP matrix is the same as above, ie,
dp[n + 1][W + 1], whereas dp[i][j] means picking the first i items with the sum of the weight less or equal to j, dp[i][j] is the maximum sum of the value.
The transit function could be as follows:
dp[i][j] = Math.max(dp[i - 1][j - k * wt[i]] + k * val[i]), where as 0<= k <= n[i]
Code (Java):
public class Solution {
public int knapSack(int W, int[] val, int[] wt, int[] n) {
if (val == null || val.length == 0 ||
wt == null || wt.length == 0 ||
n == null || n.length == 0 || W <= 0) {
return 0;
}
int[][] dp = new int[val.length + 1][W + 1];
for (int i = 1; i <= val.length; i++) {
for (int j = 0; j <= W; j++) {
for (int k = 0; k <= n[i - 1]; k++) {
if (k * wt[i - 1] <= j) {
dp[i][j] = Math.max(dp[i][j],
dp[i - 1][j - k * wt[i - 1]] + k * val[i - 1]);
}
}
}
}
return dp[val.length][W];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] val = new int[]{60, 100, 120};
int[] wt = new int[]{10, 20, 30};
int[] n = new int[]{100,100,100,100};
int W = 50;
System.out.println(sol.knapSack(W, val, wt, n));
}
}
5. A multiple back pack problem -- each item can be picked up by unlimited number of times
In this case, we only need to change little of the code above. We change the inner most loop from k <= n[i - 1] to k * wt[i - 1] <= j.
Code (Java):
public class Solution {
public int knapSack(int W, int[] val, int[] wt) {
if (val == null || val.length == 0 ||
wt == null || wt.length == 0 ||
W <= 0) {
return 0;
}
int[][] dp = new int[val.length + 1][W + 1];
for (int i = 1; i <= val.length; i++) {
for (int j = 0; j <= W; j++) {
for (int k = 0; k * wt[i - 1] <= j; k++) {
dp[i][j] = Math.max(dp[i][j],
dp[i - 1][j - k * wt[i - 1]] + k * val[i - 1]);
}
}
}
return dp[val.length][W];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] val = new int[]{60, 100, 120};
int[] wt = new int[]{10, 20, 30};
int[] n = new int[]{100,100,100,100};
int W = 50;
System.out.println(sol.knapSack(W, val, wt));
}
}
Other back pack DP problems:
1. k sum
http://buttercola.blogspot.com/2014/11/lintcode-k-sum.html
http://www.lintcode.com/en/problem/k-sum/#
Given n distinct positive integers, integer k (k <= n) and a number target.
Find k numbers where sum is target. Calculate how many solutions there are?
Example
Understand the problem:
It is another back pack problem, choosing k items out of n items, where its sum equals to k.
So we could still use back pack DP solution.
Solution:
Idea: Using back pack dp
Given [1,2,3,4], k=2, target=5. There are 2 solutions:
[1,4] and [2,3], return 2.
It is another back pack problem, choosing k items out of n items, where its sum equals to k.
So we could still use back pack DP solution.
Solution:
Idea: Using back pack dp
- Definition: dp[n + 1][k + 1][target + 1], where dp[i][j][m] means choosing j elements out of the first i elements, and its sum equals to m
- Initial state: dp[0][0][0] = 1, dp[i][0][0] = 1, 1 <= i <= n
- Transit function:
- dp[i][j][m] = dp[i - 1][j][m] // no choose item i
- if (A[i - 1] <= m) dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]] // choose item i
- Final state: dp[n][k][target];
Code (Java):
public class Solution {
/**
* @param A: an integer array.
* @param k: a positive integer (k <= length(A))
* @param target: a integer
* @return an integer
*/
public int solutionKSum(int A[],int k,int target) {
// write your code here
if ((A == null || A.length == 0) && k == 0 && target == 0) {
return 1;
}
if (A == null || A.length == 0 || k <= 0 || target <= 0 || k > A.length) {
return 0;
}
int[][][] dp = new int[A.length + 1][k + 1][target + 1];
dp[0][0][0] = 1;
for (int i = 1; i <= A.length; i++) {
dp[i][0][0] = 1;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= k; j++) {
for (int m = 1; m <= target; m++) {
dp[i][j][m] = dp[i - 1][j][m]; // no choose item i
if (A[i - 1] <= m) {
dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]]; // chose item i
}
}
}
}
return dp[A.length][k][target];
}
}
No comments:
Post a Comment