总结
1. 完全背包框架都想了半天
2. 我随机取了个背包的上限, 超时了
代码 超时
|
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
61
62
63
64
65
66
67
68 |
/* * source.cpp * * Created on: Apr 6, 2014 * Author: sangs */#include <stdio.h>#include <iostream>#include <string>#include <vector>#include <memory.h>using
namespace std;const
int INF = 0X3F3F3F3F;const
int MAXMONEY = 50000;int
val[2000];int
num[2000];int
dp[MAXMONEY+100];void
firstPass(int
n, int
target) { memset(dp, 0x3F, sizeof(dp)); dp[0] = 0; for(int
i = 0; i < n; i ++) { for(int
j = MAXMONEY; j >= val[i]; j --) { for(int
k = 0; k <= num[i]; k ++) { int
totalMoney = k*val[i]; if(j < totalMoney) continue; if(dp[j-totalMoney] == INF) continue; dp[j] = min(dp[j], dp[j-totalMoney] + k); } } }}int
secondPass(int
n, int
target) { for(int
i = 0; i < n; i ++) { for(int
j = MAXMONEY-val[i]; j >= 0; j --) { if(dp[j+val[i]] == INF) continue; dp[j] = min(dp[j], dp[j+val[i]] + 1); } } return
dp[target];}int
main() { freopen("input.txt", "r", stdin); int
n, target; while(scanf("%d%d", &n, &target) != EOF) { for(int
i = 0; i < n; i ++) { scanf("%d", val+i); } for(int
i = 0; i < n; i ++) { scanf("%d", num+i); } firstPass(n, target); int
res = secondPass(n, target); if(res == INF) res = -1; printf("%d\n", res); } return
0;} |
POJ 3260 The Fewest Coins,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhouzhuo/p/3648712.html