minimizing-coins

Minimizing Coins

CSES medium

يوجد \(n\) قطعة نقدية بقيم موجبة مختلفة. يمكنك استخدام كل قطعة أي عدد من المرات. أوجد أقل عدد من القطع مجموعها \(x\) بالضبط.

القيود:

\(1 \le n \le 100\)
\(1 \le x \le 10^6\)
\(1 \le c_i \le 10^6\)

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(x\).
السطر الثاني: \(n\) عددًا مختلفًا \(c_1, c_2, \dots, c_n\) — قيم القطع.

المخرجات:

عدد صحيح واحد — أقل عدد من القطع، أو \(-1\) إذا لم يمكن تكوين المجموع \(x\).

مثال:

الإدخال:

3 11
1 5 7

المخرجات:

(\(11 = 5 + 5 + 1\).)

الحل

نستخدم البرمجة الديناميكية مع الحالة

\(dp_s\) = أقل عدد من القطع مجموعها \(s\).

لننظر إلى القطعة الأخيرة في مجموعة مثلى من القطع مجموعها \(s\). إذا كانت قيمتها \(c_i\)، فإن باقي القطع مجموعها \(s - c_i\)، ويجب أن يكون عددها أيضًا أقل ما يمكن. لذلك

\(dp_s = \min\limits_{c_i \le s} \left( dp_{s - c_i} + 1 \right)\)

مع الحالة الأساسية \(dp_0 = 0\). إذا لم تعطِ أي قطعة مجموعًا ممكنًا \(s - c_i\)، فلا يمكن تكوين المجموع \(s\). نعلّم ذلك بقيمة كبيرة جدًا IMPOSSIBLE، وفي النهاية نطبع \(-1\) إذا بقيت \(dp_x\) مساوية لـ IMPOSSIBLE.

نحسب \(dp_s\) للقيم \(s = 1, 2, \dots, x\) بهذا الترتيب، لأن كل قيمة تستخدم مجاميع أصغر فقط.

يوجد \(x\) حالة و \(n\) انتقالًا لكل منها، لذلك التعقيد الزمني \(O(n \cdot x)\)، أي \(10^8\) عملية بسيطة على الأكثر.

#include <iostream>
#include <algorithm>
using namespace std;

const int IMPOSSIBLE = 1000000000;

int c[100];
int dp[1000001];  // dp[s] = minimum number of coins with sum s

int main() {
    int n, x;
    cin >> n >> x;

    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }

    dp[0] = 0;
    for (int s = 1; s <= x; s++) {
        dp[s] = IMPOSSIBLE;
        // the last coin can be any coin that is not larger than s
        for (int i = 0; i < n; i++) {
            if (c[i] <= s) {
                dp[s] = min(dp[s], dp[s - c[i]] + 1);
            }
        }
    }

    if (dp[x] == IMPOSSIBLE) {
        cout << -1 << "\n";
    } else {
        cout << dp[x] << "\n";
    }
}

مقارنة مع Coin Combinations I

تستخدم مسألة Coin Combinations I الحالات والانتقالات نفسها، لكنها تجمع قيم الانتقالات لتعدّ الطرق. أما هنا فنأخذ أصغرها.