Minimizing Coins

题目描述

考虑一个由 n 枚硬币组成的货币系统。每枚硬币都有一个正整数面值。你的任务是用可用的硬币组成一个总和为 x 的金额，使得硬币数量最少。 例如，如果硬币是 {1,5,7} 且目标和是 11，一个最优解是 5+5+1，需要 3 枚硬币。

输入格式

第一行输入包含两个整数 n 和 x：硬币的数量和目标金额。 第二行包含 n 个互不相同的整数 c_1,c_2,\dots,c_n：每枚硬币的面值。

输出格式

输出一个整数：最少需要的硬币数量。如果无法组成目标金额，则输出 -1。

3 11
1 5 7

3

提示

$1 \le n \le 100$ $1 \le x \le 10^6$ $1 \le c_i \le 10^6$

标签: CSES1634|动态规划|DP

来源

CSES1634|动态规划|DP