"Explanation" change exchange

Give me your money!!1

「 My question making process 」：

step1： Observation surface , This allows us to understand the type of problem solving .
  「 Write a function to calculate that you can Make up the total amount 」, It can be concluded that this is a knapsack DP.
  「 Of each coin The number is infinite 」, It is further concluded that this is Tao Completely backpack .（ Question type ： Completely backpack ）
  「 The minimum number of coins 」, Prove that this is under the premise of backpacking , Find the minimum number of components .
  「 Multiple groups Test data 」, Keep in mind that multiple sets of inputs （ On Wrong Answer With no multiple sets of inputs ）.（ Be careful ： Multi group input ）

step2： Think about the solution .
   First step , reflection dp state ：

$d{p}_{i,j}$： front $i$ A coin makes a face value $j$ Minimum number of coins .

   For the current coin $coin{s}_i$ for , Only Take or not take Two kinds of state .
   if take , Take the number of coins after as the first $i-1$ A coin makes a face value $j-w_i\times k$ The total amount of currency plus the amount of currency required for the current category $k$.
   if No , Then it means before $i-1$ These coins have been able to come up with a face value $j$, There's no need to take .

   The second step , Think about the state transfer equation ：
   The state transition equation of the original complete knapsack is ：

$$d{p}_{i,j}=\max \{d{p}_{i-1,j},d{p}_{i-1,j-a_i}+a_i\}(a_i\le j\le amount)$$

   But here we are not looking for the maximum face value within the total amount , But for The minimum number of coins to make up the total amount , So there is ：

$$d{p}_{i,j}=\min \{d{p}_{i-1,j},d{p}_{i-1,j-a_i}+1\}(a_i\le j\le amount)$$

   Through observation, we found that , The above equation Can reduce dimension . Due to $d{p}_i$ Only $i-1$, Therefore, the former dimension can be erased , But you need Guarantee $d{p}_{i,j}$ Can be $d{p}_{i,j-a_i}$ influence （ namely $d{p}_{i,j}$ When calculated $d{p}_{i,j-a_i}$ Has been worked out ）, This is the equivalent of an object $i$ It has been put into the backpack for many times , So enumerate the current face value $j$ Time should be in positive order .

   The third step , Type the code of the complete backpack , Change the state transition equation , So the algorithm part of this problem is completed ：

for (int i = 1; i <= n; i++) {
    
	for (int j = a[i]; j <= amount; j++) {
    
		dp[j] = min(dp[j], dp[j - a[i]] + 1);
	}
} 

step3： Completion code ：
   Can be found through data range , The denomination of a coin can be larger than the total amount , So you can pre-processing shallow optimization （ Although there is no big effect ）.
   Because I was looking for Minimum number of coins , therefore dp Array to be initialized to Maximum , The former $0$ Kinds of coins make up Face value $0$ It only needs $0$ Grow coins , It can be obtained. $d{p}_0=0$.
   It is worth noting that ,「 If no combination of coins can make up the total amount , Output $-1$」; In the code , It means 「 If $d{p}_{amount}$ Not updated , The output $-1$」, So we only need to judge the output $d{p}_{amount}$ If it is still the initial value, output $-1$.\

Code （ Resist academic misconduct , Refuse Ctrl + C）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5, A = 1e4 + 5, INF = 0x3f3f3f3f;
int n, amount, a[N], dp[A];
/* dp(i, j):  front  i  Put together a coin  j  The minimum number of coins  dp(i, j) = min(dp(i - 1, j - a[i]), dp(i - 1, j));  Take this coin  or  Don't take this coin  */
int main() {
    
    freopen("exchange.in", "r", stdin);
    freopen("exchange.out", "w", stdout);
    while (~scanf("%d %d", &n, &amount)) {
    
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i <= n; i++) {
    
            scanf("%d", a + i);
        }
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
    
            for (int j = a[i]; j <= amount; j++) {
    
                dp[j] = min(dp[j - a[i]] + 1, dp[j]);
            }
        }
        printf("%d\n", dp[amount] == INF ? -1 : dp[amount]); //  You can use the trinocular operator to determine 
    }
    return 0;
}

Accepted Give it to me ！！1

---

Go and solve it 『 Change for 』 beep ~ ヾ(≧▽≦*)o
Bye bye!