View Code of Problem 29

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

int a[10], b[10];
int ans[10];

// 定义不同套餐中A-I每种物品出现的次数
int pack[10][9] = {
    {1, 1, 0, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 1, 1, 0, 0, 0, 0},
    {1, 0, 0, 1, 0, 0, 1, 0, 0},
    {0, 1, 0, 1, 1, 1, 0, 1, 0},
    {0, 0, 1, 0, 0, 1, 0, 0, 1},
    {0, 1, 0, 0, 1, 0, 1, 1, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 1},
    {0, 0, 1, 0, 1, 0, 1, 0, 1},
};

bool dfs(int k) {
    if (k == 10) {
        for (int i = 0; i < 9; i++) {
            if ((a[i] + ans[i]) % 4 != 0) {
                return false;
            }
        }
        return true;
    }

    for (int i = 0; i <= b[k]; i++) {
        // 套餐包含A-I每种物品的数量
        int p[9];
        memcpy(p, pack[k], sizeof(p));
        for (int j = 0; j < 9; j++) {
            a[j] += p[j] * i;
        }

        // 更新套餐的数量
        ans[k] = i;

        // 继续搜索下一个套餐
        if (dfs(k + 1)) {
            return true;
        }

        // 回溯
        for (int j = 0; j < 9; j++) {
            a[j] -= p[j] * i;
        }
        ans[k] = 0;
    }

    return false;
}

int main() {
    memset(a, 0, sizeof(a));
    for (int i = 0; i < 9; i++) {
        cin >> b[i];
        b[i] %= 4;
    }

    dfs(1);

    // 输出答案
    for (int i = 1; i <= 9; i++) {
        for (int j = 0; j < ans[i]; j++) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}