设有n种不同面值的硬币各硬币的面值存于数组T1n中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins1n中。对任意钱数0≤m≤20001设计一个用最少硬币找钱m的方法。对于给定的1≤n≤10硬币面值数组T和可以使用的各种面值的硬币个数数组Coins以及钱数m0≤m≤20001计算找钱m的最少硬币数。用c++实现

#include #include using namespace std;

const int INF = 0x3f3f3f3f;

int n, m; int T[11], Coins[11]; int dp[20002];

int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> T[i]; } for(int i = 1; i <= n; i++) { cin >> Coins[i]; } cin >> m;

memset(dp, INF, sizeof(dp)); // 初始化为正无穷
dp[0] = 0; // 找零0元需要0个硬币

for(int i = 1; i <= n; i++) { // 枚举硬币种类
    for(int j = 0; j <= m; j++) { // 枚举找零金额
        if(dp[j] != INF) { // 如果当前金额可达
            for(int k = 0; k <= Coins[i] && k * T[i] <= j; k++) { // 枚举使用当前硬币次数
                dp[j + k * T[i]] = min(dp[j + k * T[i]], dp[j] + k); // 更新最少硬币数
            }
        }
    }
}

if(dp[m] == INF) { // 如果无法找零
    cout << "Impossible" << endl;
} else {
    cout << dp[m] << endl;
}

return 0;