❀ 題目傳送門 ❀

https://cses.fi/problemset/task/1634

❀ 解題小技巧 ❀

我用無限背包問題的概念去想它，等於說，現在有限重為 x 的背包
而輸入為每個物品的重，價值都為 1，求最小價值。

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int num, target;
  long long dp[1000005], coins[105];
  memset(dp, 0x7f, sizeof(dp));
  dp[0] = 0;
  cin >> num >> target;
  for(int i = 0; i < num; i++){
    cin >> coins[i];
  }
  for(int i = 0; i < num; i++){
    for(int j = coins[i]; j <= target; j++){
      if(dp[j] == 0) dp[j] = dp[j - coins[i]] + 1;
      else dp[j] = min(dp[j], dp[j - coins[i]] + 1);
    }
  }
  if(dp[target] < dp[1000004]) cout << dp[target];
  else cout << -1;
  return 0;
}