0-1背包和完全背包的逆序和正序
lintcode背包問題匯總
LeetCode動(dòng)態(tài)規(guī)劃刷題記錄（一）背包問題
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)
//注意點(diǎn)1：第i行的狀態(tài)只與i-1行的狀態(tài)有關(guān)，可以用兩個(gè)一維數(shù)組pre[] and cur[]
//注意點(diǎn)2：第j列的狀態(tài)只與當(dāng)前列和之前列有關(guān)缤骨，可以從后向前逆序更新
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 背包，單次選擇尺借，最大價(jià)值
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
完全背包绊起，重復(fù)選擇，最大價(jià)值
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
完全背包燎斩，重復(fù)選擇虱歪，最多裝滿可能性
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個(gè)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 種物品和一個(gè)容量是 V 的背包师枣。
第 i 種物品最多有 si 件，每件體積是 vi萧落，價(jià)值是 wi践美。
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量铐尚，且價(jià)值總和最大拨脉。
輸出最大價(jià)值。
//基礎(chǔ)解答
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的兩個(gè)循環(huán)互換位置出錯(cuò)宣增，為什么
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]);
}
}
//二進(jìn)制優(yōu)化
//單調(diào)隊(duì)列優(yōu)化
