提交记录 #68

#include <stdio.h>

#define MAX_ITEMS 100

void find_prizes(int prices[5], int total_value, int total_count) {
    // 初始化数组
    int dp[MAX_ITEMS + 1] = {0};  // 存储每个件数对应的总价值
    int count[MAX_ITEMS + 1][5] = {0}; // 记录各个奖品的选择数量

    // 动态规划
    dp[0] = 1;  // 不选择任何商品的情况
    for (int i = 0; i < 5; i++) {
        for (int j = prices[i]; j <= total_value; j++) {
            for (int k = 1; k <= total_count; k++) {
                if (j >= prices[i] && dp[j - prices[i]] && count[k - 1][i] < total_count) {
                    dp[j] = 1; // 标记可达
                    count[k][i]++; // 更新选择的奖品数量
                }
            }
        }
    }

    // 检查结果
    for (int k = 1; k <= total_count; k++) {
        if (dp[total_value]) {
            // 输出组合
            printf("%d,%d,%d,%d,%d\n", count[k][0], count[k][1], count[k][2], count[k][3], count[k][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;
}