題目描述
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimal.
For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.
輸入
The first input line has two integers n and x: the number of coins and the desired sum of money.
The second line has n distinct integers c1,c2,...,cn: the value of each coin.
Constraints
1 ≤ n ≤ 100
1 ≤ x ≤?
1 ≤ ci ≤?
輸出
Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print -1.
樣例輸入
3 11
1 5 7樣例輸出
3思路分析
經典動態規劃，硬幣找零問題。
過濾比金額x更大的硬幣。
狀態轉移方程：dp[i]=min(當前解,使用當前硬幣的解)。
代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e9;
ll n,x,c;
int main(){cin>>n>>x;vector<ll>dp(x+1,N);vector<ll>coins;dp[0]=0;for(ll i=1;i<=n;i++){cin>>c;if(c<=x)coins.push_back(c);}for(ll c:coins){for(ll i=c;i<=x;i++){dp[i]=min(dp[i],dp[i-c]+1);}}if(dp[x]==N)dp[x]=-1;cout<<dp[x];return 0;
}（起初N的位置，我用的是LONG_MAX，WA了。因為沒考慮到dp[i-c]+1可能會溢出。）
)
