实验——投资问题

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
import java.util.Scanner;
/**
* @author chenzi
*/
public class Main {
public static void main(String[] args) {
int row = 0, col = 0;
Scanner scanner = new Scanner(System.in);
col = scanner.nextInt();
row = scanner.nextInt();
int[][] a = new int[row + 1][col];
int[][] dp = new int[row + 1][col];
for (int i = 0; i < row + 1; i++) {
for (int j = 0; j < col; j++) {
a[i][j] = scanner.nextInt();
}
}
int answer = new Main().maxProfit(dp, a, row, col);
System.out.println(answer);
}
private int maxProfit(int[][] dp, int[][] a, int row, int col) {
//
row:行（5）投资的钱，col：列（4）项目
//
初始化dp数组，因为项目一的前面没有项目可以投资，所以由表直接赋值即可
for (int i = 0; i <= row; i++) {
dp[i][0] = a[i][0];
}
//
第一层for是项目，第二层for是投资钱数，第三层for则是选择
for (int k = 1; k < col; k++) {
for (int x = 1; x <= row; x++) {
for (int i = 0; i <= x; i++) {
/**
* 状态转移方程，其实还是枚举，只是说枚举的时候是基于前面的子问题最优化：
* 将投资的方案进行了简单的选择：详见参考教材*/
dp[x][k] = Math.max(dp[x][k], a[i][k] + dp[x - i][k - 1]);
}
}
}
return dp[row][col-1];
}
}
/**
* 注意数组的类型:
* 输入a数组：
* 0 0 0 0
* 11 0 2 20
* 12 5 10 21
* 13 10 30 22
* 14 15 32 23
* 15 20 40 24
*
* 输出dp数组：
* 0 0 0 0
* 11 11 11 11
* 12 12 13 31
* 13 16 30 33
* 14 21 41 50
* 15 26 43 61
* */