# 5、背包问题 &01背包、完全背包
# AcWing 873. 欧拉函数 - AcWing
# AcWing 874. 筛法求欧拉函数
01背包问题 公式dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
# 注意优化一维dp时注意状态转移的先后顺序i和i-1
# 就是看谁先被算到，谁就作为i-1状态
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;
//ACWing
public class Main {
public static void main(String[] args) {
Main main = new Main();
main.init();
}
//容斥原理
int N = 1010;
int dp[]=new int[N];
int vs[]=new int[N];
//vs表示体积
int ws[]=new int[N];
//ws表示价值
int n, m;
//n是n个物品
//m是背包容量
int bag(){
for (int i = 1; i <= n; i++) {
for (int j = m;j>=vs[i]; j--) {
dp[j]=Math.max(dp[j],dp[j-vs[i]]+ws[i]);
}
}
return dp[m];
}
void init() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
vs[i]= sc.nextInt();
ws[i]= sc.nextInt();
}
int res=bag();
System.out.println(res);
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
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
29
30
31
32
33
34
35
36
37
38
39
40
完全背包问题 公式dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;
//ACWing
public class Main {
public static void main(String[] args) {
Main main = new Main();
main.init();
}
int N = 1010;
int dp[]=new int[N];
int vs[]=new int[N];
//vs表示体积
int ws[]=new int[N];
//ws表示价值
int n, m;
//n是n个物品
//m是背包容量
int bag(){
for (int i = 1; i <= n; i++) {
for (int j = 0;j<=m; j++) {
if(j>=vs[i])
dp[j]=Math.max(dp[j],dp[j-vs[i]]+ws[i]);
}
}
return dp[m];
}
void init() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
vs[i]= sc.nextInt();
ws[i]= sc.nextInt();
}
int res=bag();
System.out.println(res);
}
}
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
29
30
31
32
33
34
35
36
37
38
39
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
29
30
31
32
33
34
35
36
37
38
39
多重背包问题
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;
//ACWing
public class Main {
public static void main(String[] args) {
Main main = new Main();
main.init();
}
//容斥原理
int N = 1010;
int dp[][]=new int[N][N];
int vs[]=new int[N];
//vs表示体积
int ws[]=new int[N];
//ss表示物品最多的数量
int ss[]=new int[N];
//ws表示价值
int n, m;
//n是n个物品
//m是背包容量
int bag(){
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for(int k=0;k<=ss[i]&& k * vs[i] <= j;k++){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-vs[i]*k]+ws[i]*k);
}
}
}
return dp[n][m];
}
void init() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
vs[i]= sc.nextInt();
ws[i]= sc.nextInt();
ss[i]= sc.nextInt();
}
int res=bag();
System.out.println(res);
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
多重背包问题Ⅱ
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;
//ACWing
public class Main {
public static void main(String[] args) {
Main main = new Main();
main.init();
}
//容斥原理
int N = 2010;
int dp[][] = new int[N][N];
int vs[] = new int[N];
//vs表示体积
int ws[] = new int[N];
//ss表示物品最多的数量
int ss[] = new int[N];
//ws表示价值
int n, m;
//n是n个物品
//m是背包容量
void init() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int cnt = 0;
for (int i = 1; i <= n; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
int s = sc.nextInt();
int k = 1;
while (k <= s) {
cnt++;
vs[cnt] = v * k;
ws[cnt] = w * k;
s -= k;
k *= 2;
}
if (s > 0) {
cnt++;
vs[cnt] = v * s;
ws[cnt] = w * s;
}
}
n = cnt;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= vs[i])
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vs[i]] + ws[i]);
}
}
System.out.println(dp[n][m]);
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
分组背包问题
import java.sql.Statement;
import java.util.*;
import java.util.concurrent.LinkedTransferQueue;
//ACWing
public class Main {
public static void main(String[] args) {
Main main = new Main();
main.init();
}
//容斥原理
int N = 1010;
int dp[] = new int[N];
int vs[][] = new int[N][N];
//vs表示体积
int ws[][] = new int[N][N];
//ss表示物品最多的数量
int ss[] = new int[N];
//ws表示价值
int n, m;
void init() {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m= sc.nextInt();
for (int i = 1; i <= n; i++) {
ss[i] = sc.nextInt();
for (int j = 0; j < ss[i]; j++) {
vs[i][j] = sc.nextInt();
ws[i][j] = sc.nextInt();
}
}
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= 0; j -- )
for (int k = 0; k < ss[i]; k ++ )
if (vs[i][k] <= j)
dp[j] = Math.max(dp[j], dp[j - vs[i][k]] + ws[i][k]);
System.out.println(dp[m]);
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42