【Day1】美妙的dp---背包问题

C、最大报销额

最大报销额(HDU-1864)

思路:

  • 首先过滤非法的支票,这里的单项物品不是说单个物品 ,而是说种类的总量
  • 然后用 01背包使就可以了
1
2
3
4
5
for (int i = 1; i <= N; i++) {
for (int v = All; v >= L[i - 1]; v--) {
dp[v] = max(dp[v], dp[v - L[i - 1]] + L[i - 1]);
}
}

还有一点就是边界的计算

$N \le 30$, 每张发票最大额度 1000, maxn = 30*1000*100+50;,这里乘100是为了避免精度问题。

代码
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
58
59
60
#include<bits/stdc++.h>
using namespace std;

/*
01 背包问题,首先过滤出合法的发票
然后做01背包处理
F[v] = max(F[v],F[v-V[i]] + V[i])

*/

int L[3000050];
int dp[3000050];
int main() {
double all; int n;
while (~scanf("%lf%d", &all, &n) && n) {
int cnt = 0;
memset(L, 0, sizeof(L));
for (int i = 0; i < n; i++) {
bool flag = true;
double sa = 0, sb = 0, sc = 0;
double sum = 0;
int m; char Type; double s;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf(" %c:%lf", &Type, &s);
if (Type == 'A') {
sa += s;
}
else if (Type == 'B') {
sb += s;
}
else if (Type == 'C') {
sc += s;
}
else {
flag = false;
}
}
sum = sa + sb + sc;
if (sa > 600.0 || sb > 600.0 || sc > 600.0 || sum > 1000.0) {
flag = false;
}
if (flag) {
L[cnt++] = sum*100;
}
}
/*for (int i = 0; i < L.size(); i++) {
cout << "L : " << L[i] << endl;
}*/
memset(dp, 0, sizeof(dp));
int All = (int)(all * 100 + 0.5);
int N = cnt;
for (int i = 1; i <= N; i++) {
for (int v = All; v >= L[i - 1]; v--) {
dp[v] = max(dp[v], dp[v - L[i - 1]] + L[i - 1]);
}
}
printf("%.2lf\n", 1.0*dp[All]/100.0);
}
}

D、FATE

Fate(HDU-2159)

题意:
还需要 n 经验升一级
有 m 的忍耐度
有 k 种怪物
最多杀 s 只怪物

问能否升级,若能升级,则输出剩余的最大忍耐度

思路
就是一个完全背包问题,设 $dp[i][j]$ 表示花费耐力值 $i$ ,最多杀 $j$ 只怪物的情况下所获得的最大经验值

状态转移方程:

其中的 $i$ 表示杀前 $i$ 种怪, $j$,$k$ 分别表示杀怪数和耗费的耐力值

代码
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
/*
思路:
完全背包
*/

#include<bits/stdc++.h>
using namespace std;

int dp[110][110];
int A[110]; //exp
int B[110];
int n, m, k, s;

int main() {
while (~scanf("%d%d%d%d", &n, &m, &k, &s)) {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < k; i++) {
scanf("%d%d", A + i, B + i);
}
for (int i = 0; i < k; i++) {
for (int j = 1; j <= s; j++) {
for (int l = B[i]; l <= m; l++) {
dp[j][l] = max(dp[j][l], dp[j - 1][l - B[i]] + A[i]);
}
}
}
int flag = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= s; j++) {
if (dp[j][i] >= n) {
printf("%d\n", m - i);
flag = 1;
break;
}
}
if (flag) {
break;
}
}
if (!flag) {
printf("-1\n");
}
}
}