解题思路:用01背包的动态规划解法来写
注意事项:注意输入的转换以及数组的下标问题,为了方便表示把结果的dp数组的第一位置零
参考代码:
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
String[] input = scan.nextLine().split(" ");
int Time = Integer.parseInt(input[0]);
int Type = Integer.parseInt(input[1]);
int[] time = new int[Type];
int[] value = new int[Type];
for (int i = 0; i < Type; i++) {
input = scan.nextLine().split(" ");
time[i] = Integer.parseInt(input[0]);
value[i] = Integer.parseInt(input[1]);
}
scan.close();
System.out.println(findmed(Time,Type,time,value));
}//main
public static int findmed (int T, int type, int[] time, int[] value) {
int[] dp = new int[T+1];
for (int i = 1; i < type + 1; i++) {
for (int j = T; j >= time[i-1]; j--) {
dp[j] = Math.max(dp[j], dp[j-time[i-1]] + value[i-1]);
}
}
return dp[T];
}
}//Class Main
0.0分
1 人评分