問題描述

現在 康康 手上有 n 種不同面值的硬幣，每種硬幣有無限多個。為了方便購物，他希望帶盡量少的硬幣，但是要能組合出 1 到 m 之間的任意值。

輸入格式

第一行為兩個整數：m 和 n，他們的意義如題目描述。
接下來的 n 行，每行一個整數，第 i+1 行的整數表示第 i 種硬幣的面值

輸出格式

最少需要攜帶的硬幣數量，如果無解則輸出-1。

樣例輸入

20 4
1
2
5
10

樣例輸出

5

解題代碼

import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String[] args) {int sum = 0;int ans = 0;Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();int[] list = new int[n + 1];for (int i = 1; i <= n; i++) {list[i] = scanner.nextInt();}Arrays.sort(list);if (list[1] != 1) {System.out.print(-1);}while (true) {if (sum >= m) {System.out.println(ans);break;}for (int i = n; i >= 1; i--) {if (list[i] <= sum + 1) {sum += list[i];ans++;break;}}}} }

結果

總結

以上是生活随笔為你收集整理的2019春季暑期实习生正式批招聘笔试【腾讯】（回忆版）第二题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。