提交记录 #67

#include <stdio.h>

#define MAX_ITEMS 1000

void find_prizes(int prices[5], int total_value, int total_count) {
    int dp[MAX_ITEMS + 1] = {0}; // 存储每个总价值的可能组合
    int count[MAX_ITEMS + 1] = {0}; // 记录组合的数量
    int current_count[5] = {0}; // 用于输出的当前组合

    // 初始化状态
    for (int i = 0; i <= total_count; i++) {
        dp[i] = -1; // 初始化为-1表示不可达
    }
    dp[0] = 0; // 不选择任何商品的情况

    // 动态规划
    for (int i = 0; i < 5; i++) {
        for (int j = total_count; j >= 0; j--) {
            for (int k = 1; k <= total_count - j; k++) {
                int new_value = dp[j] + k * prices[i];
                int new_count = j + k;
                if (new_count <= total_count && (dp[new_count] == -1 || new_value < dp[new_count])) {
                    dp[new_count] = new_value;
                    count[new_count] = i; // 记录来自哪种奖品
                }
            }
        }
    }

    // 输出符合条件的组合
    for (int j = 0; j <= total_count; j++) {
        if (dp[j] == total_value) {
            // 输出当前组合
            for (int k = 0; k < 5; k++) {
                current_count[k] = 0;
            }
            int rem_count = j;
            while (rem_count > 0) {
                current_count[count[rem_count]]++;
                rem_count--;
            }
            printf("%d,%d,%d,%d,%d\n", current_count[0], current_count[1], current_count[2], current_count[3], current_count[4]);
        }
    }
}

int main() {
    int prices[5];
    int total_value, total_count;

    // 输入奖品价格
    for (int i = 0; i < 5; i++) {
        scanf("%d", &prices[i]);
    }

    // 输入总价值和总件数
    scanf("%d %d", &total_value, &total_count);

    // 查找符合条件的奖品组合
    find_prizes(prices, total_value, total_count);

    return 0;
}