动态规划求解"疯狂的采药"问题(洛谷P1616题题解,Java语言描述)
程序员文章站
2022-07-16 12:30:09
...
题目要求
分析
参考这篇文章自己做出来的 → Here
我就不讲了。
AC代码(Java语言描述)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int time = scanner.nextInt(), num = scanner.nextInt();
int[] f = new int[time+1];
int[] cost = new int[num], value = new int[num];
for (int i = 0; i < num; i++) {
cost[i] = scanner.nextInt();
value[i] = scanner.nextInt();
}
scanner.close();
for (int i = 0; i < num; i++) {
for (int j = cost[i]; j <= time; j++) {
if (j >= cost[i]) {
f[j] = Math.max(f[j], f[j-cost[i]]+value[i]);
}
}
}
System.out.println(f[time]);
}
}
上一篇: 完全背包问题(模板)