题目
你要出去旅游,有N元的预算住酒店,有M家酒店供你挑选,这些酒店都有价格X。
需要你正好花完这N元住酒店(不能多,也不能少)最少能住几晚?返回最少住的天数,没有匹配的返回-1
- 比如你有1000元,所有酒店都是大于1000的,则返回-1
- 比如你有1000元,有1家1000元的,有1家300,有1家700。则最少能住1晚,最多住2晚(300+700)。返回1
- 比如你有1000元,有1家387元,有1家2元,有一家611,则返回3(3家各住1天)
- 比如你有1000元,有1家1元的,有一家2元的,有一家1001元的,则返回500(1元的1000天,2元的500天)
代码
import java.util.Arrays; import java.util.List; import java.util.Scanner; import java.util.stream.Collectors; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); List<Integer> list = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList()); int money = list.remove(list.size() - 1); int[] dp = new int[money + 1]; for (int i = 1; i <= money; i++) { dp[i] = Integer.MAX_VALUE; if (i >= list.get(0) && dp[i - list.get(0)] != Integer.MAX_VALUE) { dp[i] = dp[i - list.get(0)] + 1; } } for (int i = 1; i <= money; i++) { for (int j = 0; j < list.size(); j++) { if (i >= list.get(j) && dp[i - list.get(j)] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[i - list.get(j)] + 1); } } } if (dp[money] != Integer.MAX_VALUE) { System.out.println(dp[money]); } else { System.out.println(-1); } } }