算法
1.前缀和
前缀和核心代码
)
差分数组
重点理解：
2.动态规划
最长递增子序列
最大子数组和问题
洛谷
1.NASA的食物计划——01 背包dp
题目描述
航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.
输入格式
第一行 两个数 体积最大值(<400)和质量最大值(<400)
第二行 一个数 食品总数N(<50).
第三行－第3+N行
每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)
输出格式
一个数 所能达到的最大卡路里(int范围内)
输入输出样例
输入 #1
1
2
3
4
5
6
| 320 350
4
160 40 120
80 110 240
220 70 310
40 400 220
|
输出 #1
1.分析一下题目可知这是典型的背包问题 即食物的体积作为0，质量作为1，而卡路里则为每个食物的价值。分别定义三个数组：分别用来接收体积、质量、还有卡路里的值。
2.接下来就是状态选择：
1
2
3
| for 状态1 in 状态1 的所有取值 ：
for 状态2 in 状态2的所有取值：
dp[状态1][状态2]=择优（选择1，选择2）
|
3.定义Base case的起点为最大值。每次状态转移判断是否大于选择的量，若大于则j–，k–。
4.写出状态转移方程：
1
2
3
4
5
| dp[j][k]=Math.max(dp[j][k],dp[j-V[i][k-M[i]]+K[i])
dp[j][k] 即保持原来的状态
dp[j-V[i][k-M[i]]+K[i] 首先j-V[i] 就是将食品放入背包后剩下的体积。 而k-M[i]同理即为剩下的质量。 最后加上放入食品的卡路里值，即K[i]。
|
完整代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class g20 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int MaxV = scanner.nextInt();
int MaxM = scanner.nextInt();
int N = scanner.nextInt();
int [][] dp = new int[MaxV+1][MaxM+1];
int [] V =new int[N];
int [] M = new int[N];
int [] K = new int[N];
for (int i = 0; i <N ; i++) {
V[i] =scanner.nextInt();
M[i] =scanner.nextInt();
K[i] = scanner.nextInt();
for (int j = MaxV; j >=V[i] ; j--) {
for (int k = MaxM; k >=M[i] ; k--) {
dp[j][k] =Math.max(dp[j][k],dp[j-V[i]][k-M[i]]+K[i]);
}
}
}
System.out.println(dp[MaxV][MaxM]);
}
}
|
