6个月前

### 题目描述（混合背包问题）

si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；

0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000

#### 样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

8


### 算法:(分情况讨论)

#### Java 代码

import java.util.*;
public class Main {
public static int backPack7(int N, int V, int[] v, int[] w, int[] s) {
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
if (s[i] == 0) {
for (int j = v[i]; j <= V; j++) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
} else if (s[i] == -1) {
for (int j = V; j >= v[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
} else {
for (int j = V; j >= 0; j--) {
for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
System.out.println(backPack7(N, V, v, w, s));
}
}


### 题目描述(二维费用背包)

0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000

#### 样例

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

8


### 算法:(暴力枚举)

#### Java 代码

import java.util.*;
public class Main {
public static int backPack8(int N, int V, int M, int[] v, int[] m, int[] w) {
int[][] dp = new int[V + 1][M + 1];
for (int i = 0; i < N; i++) {
for (int j = V; j >= v[i]; j--) {
for (int k = M; k >= m[i]; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);
}
}
}
return dp[V][M];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int M = sc.nextInt();
int[] v = new int[N];
int[] m = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
m[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(backPack8(N, V, M, v, m, w));
}
}


### 题目描述(分组背包)

0<N,V≤100
0<Si≤100
0<vij,wij≤100

#### 样例

3 5
2
1 2
2 4
1
3 4
1
4 5

8


### 算法:(暴力枚举)

#### Java 代码

import java.util.*;
public class Main {
public static int backPack9(int N, int V, int[][] v, int[][] w) {
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
int len = v[i].length;
for (int j = V; j >= 0; j--) {
for (int k = 0; k < len; k++) {
if (j >= v[i][k]) dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);
}
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[][] v = new int[N][];
int[][] w = new int[N][];
for (int i = 0; i < N; i++) {
int s = sc.nextInt();
v[i] = new int[s];
w[i] = new int[s];
for (int j = 0; j < s; j++) {
v[i][j] = sc.nextInt();
w[i][j] = sc.nextInt();
}
}
System.out.println(backPack9(N, V, v, w));
}
}


6个月前

### 题目描述

0<N≤1000
0<V≤20000
0<vi,wi,si≤20000

#### 样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

10


### 回顾

#### Java 代码

import java.util.*;
public class Main {
public static int backPack3(int N, int V, int[] v, int[] w, int[] s) {
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
// this is wrong, in this case we are acturely doing 0-1 backpack using 0v[i], 1v[i]...s[i]v[i]
// for (int k = 0; k <= s[i]; k++) {
//     for (int j = V; j >= k * v[i]; j--) {
//         dp[j] = Math.max(dp[j], dp[j -  k * v[i]] + k * w[i]);
//     }
// }

// this is correct, only 1 case for k * v[i]
for (int j = V; j >= 0; j--) {
for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
System.out.println(backPack3(N, V, v, w, s));
}
}


### 算法1

#### Java 代码

import java.util.*;
public class Main {
public static int backPack4(int V, List<Integer> vList, List<Integer> wList) {
int[] dp = new int[V + 1];
for (int i = 0; i < vList.size(); i++) {
for (int j = V; j >= vList.get(i); j--) {
dp[j] = Math.max(dp[j], dp[j - vList.get(i)] + wList.get(i));
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
List<Integer> vList = new ArrayList<>();
List<Integer> wList = new ArrayList<>();
for (int i = 0; i < N; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
int s = sc.nextInt();
}
if (s > 0) {
}
}
System.out.println(backPack4(V, vList, wList));
}
}


### 算法2

#### Java 代码

import java.util.*;
/*
*1. for an item with v and w to fill package j, only consider the cases:
*   dp[j - v] + w, dp[j - 2 * v] + 2 * w, ... , dp[j - k * v] + k * w (k = min(s[i], j / v));
*2. f(i) = dp[j - i * v] + i * w, we want to get f(1), f(2), ... ,f(k) dynamicaly, could use Monotone Queue;
*3. time complexity: O(N * V)
*/
public class Main {
public static int backPack5(int N, int V, int[] v, int[] w, int[] s) {
int[] dp = new int[V + 1];
int[] copy = new int[V + 1];
int[] queue = new int[V + 1];
for (int i = 0; i < N; i++) {
// for index i, copy arr stores the result only using item before i
for (int c = 0; c <= V; c++) copy[c] = dp[c];
// status only transfer amone mode v has same result
for (int j = 0; j < v[i]; j++) {
// use 2 pointer to simulat monotone queue
int tail = -1;
for (int k = j; k <= V; k += v[i]) {
while (head <= tail && copy[k] >= copy[queue[tail]] + (k - queue[tail]) / v[i] * w[i]) tail--;
queue[++tail] = k;
}
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
System.out.println(backPack5(N, V, v, w, s));
}
}


6个月前

### 题目描述

0-1背包

0<N,V≤1000
0<vi,wi≤1000

#### 样例

4 5
1 2
2 4
3 4
4 5

8


O(NV)

#### Java 代码

import java.util.*;
public class Main {
public static int backPack1(int N, int V, int[] v, int[] w) {
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
for (int j = V; j >= v[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(backPack1(N, V, v, w));
}
}


### 题目描述

0<N,V≤1000
0<vi,wi≤1000

#### 样例

4 5
1 2
2 4
3 4
4 5

10


O(NV)

#### Java 代码

import java.util.*;
public class Main {
public static int backPack2(int N, int V, int[] v, int[] w) {
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
for (int j = v[i]; j <= V; j++) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(backPack2(N, V, v, w));
}
}


### 题目描述

0<N,V≤100
0<vi,wi,si≤100

#### 样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

10


O(NVS)

#### Java 代码

import java.util.*;
public class Main {
public static int backPack3(int N, int V, int[] v, int[] w, int[] s) {
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
// this is wrong, in this case we are acturely doing 0-1 backpack using 0v[i], 1v[i]...s[i]v[i]
// for (int k = 0; k <= s[i]; k++) {
//     for (int j = V; j >= k * v[i]; j--) {
//         dp[j] = Math.max(dp[j], dp[j -  k * v[i]] + k * w[i]);
//     }
// }

// this is correct, only 1 case for k * v[i]
for (int j = V; j >= 0; j--) {
for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
return dp[V];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
System.out.println(backPack3(N, V, v, w, s));
}
}