4 “quả bóng” (giống như 4 mệnh giá tiền) Tìm số lượng mỗi quả

 

Ta có 4 “quả bóng” (giống như 4 mệnh giá tiền):

Quả	Giá trị
A	18
B	11
C	7
D	1

Mục tiêu:
Tìm số lượng mỗi quả (x, y, z, t) sao cho:

18x + 11y + 7z + 1t = N

và tổng số quả (x + y + z + t) là nhỏ nhất.

---

🧮 Ví dụ: N = 22

Ta có thể giải thủ công:

• Nếu lấy 1 quả A (18) ⇒ còn 4 → cần 4 quả D (1).
  Tổng: 1 + 4 = 5 quả.

• Nếu lấy 2 quả B (11×2 = 22) ⇒ đủ.
  Tổng: 2 quả ✅ (rất tốt).

• Nếu lấy 3 quả C (7×3 = 21), còn 1 → thêm 1 quả D.
  Tổng: 3 + 1 = 4 quả.

➡️ Kết quả tối ưu là x=0, y=2, z=0, t=0 với tổng 2 quả.

---

✅ Cách viết hàm tổng quát trong C#

Dưới đây là một đoạn code C# để tìm nghiệm tối ưu cho mọi số N nhỏ gọn, dễ hiểu:

using System;

class Program
{
    static void Main()
    {
        int[] values = { 18, 11, 7, 1 };
        string[] names = { "A", "B", "C", "D" };
        int target = 22;

        var result = FindMinBalls(values, target);
        Console.WriteLine($"Target = {target}");
        Console.WriteLine($"A={result[0]}, B={result[1]}, C={result[2]}, D={result[3]}");
        Console.WriteLine($"Total balls = {result[0] + result[1] + result[2] + result[3]}");
    }

    static int[] FindMinBalls(int[] values, int target)
    {
        int[] best = new int[values.Length];
        int minCount = int.MaxValue;

        // Brute-force tối ưu vì chỉ có 4 loại bóng
        for (int a = 0; a <= target / values[0]; a++)
        {
            for (int b = 0; b <= target / values[1]; b++)
            {
                for (int c = 0; c <= target / values[2]; c++)
                {
                    int sum = 18 * a + 11 * b + 7 * c;
                    if (sum > target) continue;
                    int d = target - sum; // giá trị còn lại sẽ là bóng D (1 điểm mỗi quả)
                    int count = a + b + c + d;
                    if (count < minCount)
                    {
                        minCount = count;
                        best[0] = a;
                        best[1] = b;
                        best[2] = c;
                        best[3] = d;
                    }
                }
            }
        }

        return best;
    }
}

---

🧠 Giải thích

• Duyệt qua tất cả số lượng bóng A, B, C có thể.

• Tính tổng giá trị hiện có.

• Số còn lại được bù bằng bóng D.

• So sánh tổng số bóng để chọn phương án ít nhất.

---

📊 Kết quả ví dụ

Với target = 22, chương trình in ra:

Target = 22
A=0, B=2, C=0, D=0
Total balls = 2


==========================================================

version Dynamic Programming O(n × target) cho bài toán Coin Change – Minimum Coins (tìm số lượng bóng ít nhất để đạt target).

✅ Ý tưởng
Ta dùng mảng:
dp[i] = số bóng ít nhất để đạt tổng i

Công thức:
dp[i] = min(dp[i], dp[i - value] + 1)


🚀 Version DP tối ưu (khuyên dùng)
static int[] FindMinBallsDP(int[] values, int target)
{
    int n = values.Length;
    int[] dp = new int[target + 1];
    int[] lastUsed = new int[target + 1]; // lưu index value được dùng cuối

    // Khởi tạo
    for (int i = 1; i <= target; i++)
        dp[i] = int.MaxValue;

    dp[0] = 0;

    // DP O(n × target)
    for (int i = 1; i <= target; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (values[j] <= i && dp[i - values[j]] != int.MaxValue)
            {
                if (dp[i - values[j]] + 1 < dp[i])
                {
                    dp[i] = dp[i - values[j]] + 1;
                    lastUsed[i] = j;
                }
            }
        }
    }

    // Không có nghiệm
    if (dp[target] == int.MaxValue)
        return null;

    // Truy vết kết quả
    int[] result = new int[n];
    int t = target;

    while (t > 0)
    {
        int index = lastUsed[t];
        result[index]++;
        t -= values[index];
    }

    return result;
}


📌 Độ phức tạp


Time: O(n × target)


Space: O(target)