背包九讲-学习心得

背包九讲-学习心得

01背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;
public class Main{
static final int N = 1010;
private int[][] F = new int[N][N];
public void ccc(){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] w = new int[n+1];
int[] v = new int[n+1];
for(int i = 1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i=1;i<=n;i++){
for(int j = 1;j<=m;j++){
F[i][j] = F[i-1][j];
if(j>=v[i])
F[i][j] = Math.max(F[i][j],F[i-1][j-v[i]]+w[i]);
}
}
System.out.println(F[n][m]);
}
public static void main(String[] args){
Main a = new Main();
a.ccc();
}
}

代码优化

将二维数组降低为一维数组,来减小空间复杂度,但是时间复杂度并没有因此而减小,这点需要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Scanner;
public class Main{
static final int N = 1010;
private int[] F = new int[N];
public void ccc(){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] w = new int[n+1];
int[] v = new int[n+1];
for(int i = 1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
F[j] = Math.max(F[j],F[j-v[i]] + w[i]);
}
}
System.out.println(F[m]);
}
public static void main(String[] args){
Main a = new Main();
a.ccc();
}
}

完全背包问题

多重背包问题

混合背包问题

二维费用的背包问题

分组背包问题

背包问题求方案数

求背包问题的方案

有依赖的背包问题

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------