0-1背包和完全背包的逆序和正序
lintcode背包问题汇总
LeetCode动态规划刷题记录（一）背包问题
ACWing中有足够的背包问题
-
92. Backpack
0-1背包，单次选择，最大体积
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
//time: O(nm) space: O(nm)
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 n = A.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; 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]] + A[i-1]);
}
}
}
return dp[n][m];
}
}
//time: O(nm) space: O(nm)
//注意点1：第i行的状态只与i-1行的状态有关，可以用两个一维数组pre[] and cur[]
//注意点2：第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 n = A.length;
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {
for (int j = m; j >= A[i-1]; j--) {
dp[j] = Math.max(dp[j], dp[j-A[i-1]] + A[i-1]);
}
}
return dp[m];
}
}
-
125. Backpack II
0-1 背包，单次选择，最大价值
There are n items and a backpack with size m. Given array A representing the size of each item and array V representing the value of each item. What's the maximum value can you put into the backpack?
//time: O(nm) space: O(nm)
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 n = A.length;
int[][] dp = new int[n + 1][m + 1];
//dp[i][j] means the max value when we have considered the first i items with size j
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (j < A[i-1]) {
//don't consider the item
dp[i][j] = dp[i-1][j];
} else {
//consider it, add/not add it can we have more values
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
}
}
}
return dp[n][m];
}
}
//time: O(nm) space: O(m)
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 n = A.length;
int[] dp = new int[m + 1];
//dp[i][j] means the max value when we have considered the first i items with size j
for (int i = 1; i <= n; i++) {
for (int j = m; j >= A[i-1]; j--) {
dp[j] = Math.max(dp[j], dp[j-A[i-1]] + V[i-1]);
}
}
return dp[m];
}
}
- 背包3
完全背包，重复选择，最大价值
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?
//time: O(nm) space: O(nm)
public class solution {
public int backpackIII(int[] A, int[] V, int m) {
int n = A.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//注意后者是dp[i][xxx] 不是 dp[i-1][xxx]
if (j >= A[i-1])
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-A[i-1]] + V[i-1]);
}
}
return dp[n][m];
}
}
//time: O(nm) space: O(m)
public class solution {
public int backpackIII(int[] A, int[] V, int m) {
int n = A.length;
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= A[i-1])
dp[j] = Math.max(dp[j], dp[j-A[i-1]] + V[i-1]);
}
}
return dp[m];
}
}
-
562. Backpack IV
完全背包，重复选择，最多装满可能性
Given an integer array nums[] which contains n unique positive numbers, num[i] indicate the size of ith item. An integer target denotes the size of backpack. Find the number of ways to fill the backpack. Each item may be chosen unlimited number of times.
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[] nums, int target) {
// write your code here
int n = nums.length;
int[][] dp = new int[n + 1][target + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 1; //有前i个item，得到weight为0的方式为1
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] + dp[i][j - nums[i-1]];
}
}
}
return dp[n][target];
}
}
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[] nums, int target) {
// write your code here
int n = nums.length;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= target; j++) {
if (nums[i] == j) dp[j] += 1;
else if (nums[i] < j) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
-
563. Backpack V
0-1背包，单次选择，最多装满可能性
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
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 n = nums.length;
int[][] dp = new int[n + 1][target + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];
}
}
}
return dp[n][target];
}
}
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 n = nums.length;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
- 多重背包
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
//基础解答
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int V = in.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
int[] s = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
s[i] = in.nextInt();
}
in.close();
//核心代码
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
for (int j = V; j >= 0; j--) { //j和k的两个循环互换位置出错，为什么
for (int k = 0; k <= s[i]; k++) {
if (j >= k*v[i])
dp[j] = Math.max(dp[j], dp[j - k*v[i]] + k*w[i]);
}
}
}
System.out.println(dp[V]);
}
}
//二进制优化
//单调队列优化
