Live Note

Remain optimistic

01背包问题

问题描述

背包： 总重 M
物品数量： S
物品： 重量 thingM ，价值 thingT
需求：在背包能够承受的重量下，装下价值大的物品
输入格式
第一行为 2 个数字，分别为背包的总重 M 和物品的数量 S
接下来的 M 行为每个物品的重量 thingM 以及物品的价值 thingT
M <= 100 且 S <= 1000
输出格式
一个整数，代表能拿到的最大的价值

样例数据

1
2
3
4
70 3
71 100
69 1
1 2

分析问题

01 背包问题就在于一个物品，只有两种情况：拿或者不拿。
这时就可以进行判断：

  1. 重量允许的情况下，拿价值高的方案
  2. 重量不允许则不拿

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Scanner input = new Scanner(System.in);
int dp[][] = new int[101][1001];
int M = input.nextInt(),
S = input.nextInt();
for (int i = 1; i <= S; i++) {
int thingM = input.nextInt(),
thingT = input.nextInt();
for (int j = 1; j <= M; j++) {
if (j >= thingM) { // 可以拿
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - thingM] + thingT);
} else dp[i][j] = dp[i - 1][j]; // 不拿
}
}
System.out.println(dp[S][M]);

输出
3

例题 2

一辆车，总共可以装 M 质量的物品，有 N 件物品，每件物品重 thingM 。
能装的都装完后，还能剩下多少质量？
输入格式
第一行为一个整数，代表车的容量 M 。
第二行为一个整数，代表物品数量 N 。
接下来的 N 行，代表每个物品的重量。
0 <= M <= 20000 且 0 <= N <= 20
输出格式
一个整数，代表剩余容量。
样例数据

1
2
3
4
5
6
7
8
24
6
8
3
12
7
9
7

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[][] = new int[31][20001];
Scanner input = new Scanner(System.in);
int V = input.nextInt(),
Len = input.nextInt();
for (int i = 1; i <= Len; i++) {
int thingS = input.nextInt();
for (int j = 1; j <= V; j++) {
if (j >= thingS) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - thingS] + thingS);
} else dp[i][j] = dp[i - 1][j];
}
}
System.out.println(V - dp[Len][V]);

输出
0