总结
1. 偏移的设置又思考了很久, 实际上, 枚举几个例子就能把思路找出来
2. dp[i][j], 循环的最外两层循环分别是 i, j
3. 初始化问题, dp[i][j] 初始化成 0 更好, 下面的代码写的很丑, 就是因为初始化没搞好. 做题时若实在拿捏不准到底初始化成 0, 1 还是 INF, 那就都试试
代码
|
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 |
/* * source.cpp * * Created on: Apr 5, 2014 * Author: sangs */#include <stdio.h>#include <iostream>#include <string>#include <vector>#include <memory.h>using
namespace std;const
int INF = 0X80808080;int
dp[30][20000];int
pos[1000];int
weight[1000];int
cal(int
n, int
m) { memset(dp, 0x80, sizeof(dp)); dp[0][7500] = 1; for(int
i = 1; i <= m; i ++) { // enum weight for(int
j = 0; j <= 15000; j ++) { // enum balance value for(int
k = 1; k <= n; k ++) { // enum position if(dp[i-1][j] == INF) continue; int
newBalance = (pos[k]*weight[i]) + j; if(dp[i][newBalance] == INF) { dp[i][newBalance] = dp[i-1][j]; }else
{ dp[i][newBalance] += dp[i-1][j]; } //printf("dp[%d][%d] = %d\n", i, newBalance-7500, dp[i][newBalance]); } } } if(dp[m][7500] == INF) return
0; return
dp[m][7500];}int
main() { freopen("input.txt", "r", stdin); int
n, m; while(scanf("%d%d", &n, &m) != EOF) { for(int
i = 1; i <= n; i ++) scanf("%d", pos+i); for(int
i = 1; i <= m; i ++) scanf("%d", weight+i); int
res = cal(n, m); printf("%d\n", res); } return
0;} |
POJ 1837 Balance(二维DP),布布扣,bubuko.com
原文：http://www.cnblogs.com/zhouzhuo/p/3648544.html