C 語言解「小明送外賣」整數規劃問題

題目：開封菜 20 元、麥當勞 12 元、必勝客 8 元。共送 n 份、收入 m 元，求三者份數（多解時開封菜降序、麥當勞降序）。無解輸出 No Solution。

數學模型

k + c + p = n
20k + 12c + 8p = m
k, c, p ≥ 0 且為整數

代入 p = n - k - c，得 20k + 12c + 8(n - k - c) = m → 12k + 4c = m - 8n。雙重迴窮舉 k、c 即可。

完整程式碼

#include <stdio.h>
#include <stdbool.h>

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) == 2)
    {
        bool found = false;
        for (int k = n; k >= 0; k--)           // 開封菜降序
        {
            for (int c = n - k; c >= 0; c--)   // 麥當勞降序
            {
                int p = n - k - c;
                if (p < 0) continue;
                if (20*k + 12*c + 8*p == m)
                {
                    printf("%d %d %d\n", k, c, p);
                    found = true;
                }
            }
        }
        if (!found) printf("No Solution\n");
    }
    return 0;
}

複雜度 O(n²)，n ≤ 100 時極快。若 n 極大可用數學推導降為 O(n)。