苞米探长 2024-11-21 01:35 采纳率: 36.4%
浏览 16

如何用c语言解决凑零钱问题

凑零钱

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有 10 4 枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。

【输入格式】

输入第一行给出两个正整数:N(≤104 )是硬币的总个数,M(≤102 )是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

【输出格式】

在一行中输出硬币的面值 V1≤V2 ≤⋯≤Vk ,满足条件 V1 +V2 +...+Vk =M。数字间以 1 个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出 No Solution。

注:我们说序列{ A[1],A[2],⋯ }比{ B[1],B[2],⋯ }“小”,是指存在 k≥1 使得 A[i]=B[i] 对所有 i<k 成立,并且 A[k]<B[k]。

【输入样例 1】

8 9

5 9 8 7 2 3 4 1

【输出样例 1】

1 3 5

【输入样例 2】

4 8

7 2 4 3

【输出样例 2】

No Solution

  • 写回答

1条回答 默认 最新

  • 月下独码 Java领域新星创作者 2024-11-22 10:45
    关注

    本答案参考 多次询问 ChatGPT-3.5 后选择的最佳回答,若是满意,还请采纳,谢谢

    1. 问题分析
      • 这是一个典型的凑零钱问题,可以使用动态规划来解决。动态规划的关键是定义状态和状态转移方程。
      • 定义dp[i][j]表示前i个硬币能否凑出金额j
      • 状态转移方程为:dp[i][j]=dp[i - 1][j] || dp[i - 1][j - coins[i]],其中coins[i]是第i个硬币的面值。
      • 为了输出最小序列,我们可以从后往前推导选择了哪些硬币。
    2. 代码实现如下
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    // 比较两个数组大小,用于输出最小序列
    bool isSmaller(int* arr1, int* arr2, int len) {
        for (int i = 0; i < len; i++) {
            if (arr1[i] < arr2[i]) {
                return true;
            } else if (arr1[i] > arr2[i]) {
                return false;
            }
        }
        return false;
    }
    
    // 输出凑出金额的硬币组合
    void printCoins(int* coins, int* selected, int n) {
        int flag = 0;
        for (int i = 0; i < n; i++) {
            if (selected[i]) {
                if (flag) {
                    printf(" ");
                }
                printf("%d", coins[i]);
                flag = 1;
            }
        }
        printf("\n");
    }
    
    // 解决凑零钱问题
    void coinChange(int* coins, int n, int m) {
        bool** dp = (bool**)malloc((n + 1) * sizeof(bool*));
        for (int i = 0; i <= n; i++) {
            dp[i]=(bool*)malloc((m + 1) * sizeof(bool));
        }
        // 初始化边界条件
        for (int i = 0; i <= n; i++) {
            dp[i][0]=true;
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j]=false;
        }
        // 动态规划计算
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j < coins[i - 1]) {
                    dp[i][j]=dp[i - 1][j];
                } else {
                    dp[i][j]=dp[i - 1][j] || dp[i - 1][j - coins[i - 1]];
                }
            }
        }
        if (!dp[n][m]) {
            printf("No Solution\n");
            return;
        }
        // 回溯找出最小的硬币组合
        int* selected = (int*)malloc(n * sizeof(int));
        int* minSelected = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            minSelected[i]=0;
        }
        int amount = m;
        for (int i = n; i > 0; i--) {
            if (dp[i - 1][amount]) {
                selected[i - 1]=0;
            } else {
                selected[i - 1]=1;
                amount -= coins[i - 1];
            }
        }
        for (int i = 0; i < n; i++) {
            minSelected[i]=selected[i];
        }
        for (int i = 1; i <= n; i++) {
            // 重新构建一个可能的组合
            int newAmount = m;
            int* newSelected = (int*)malloc(n * sizeof(int));
            for (int j = 0; j < n; j++) {
                newSelected[j]=0;
            }
            for (int j = n; j > 0; j--) {
                if (dp[j - 1][newAmount]) {
                    newSelected[j - 1]=0;
                } else {
                    newSelected[j - 1]=1;
                    newAmount -= coins[j - 1];
                }
            }
            if (isSmaller(newSelected, minSelected, n)) {
                for (int k = 0; k < n; k++) {
                    minSelected[k]=newSelected[k];
                }
            }
            free(newSelected);
        }
        printCoins(coins, minSelected, n);
        free(selected);
        free(minSelected);
        for (int i = 0; i <= n; i++) {
            free(dp[i]);
        }
        free(dp);
    }
    
    
    int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        int* coins = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            scanf("%d", &coins[i]);
        }
        coinChange(coins, n, m);
        free(coins);
        return 0;
    }
    
    
    1. 代码解释
      • isSmaller函数中,比较两个数组的大小,按照题目中定义的序列大小关系进行比较。
      • printCoins函数用于输出凑出金额的硬币组合。
      • coinChange函数中:
        • 首先动态分配二维数组dp,并初始化边界条件。
        • 然后通过动态规划计算dp数组的值。
        • 如果dp[n][m]false,表示无解,输出No Solution
        • 否则,通过回溯找出一种硬币组合,再通过循环比较找出最小的硬币组合并输出。
      • main函数中,读取输入的硬币个数n、付款金额m和硬币面值数组coins,然后调用coinChange函数解决问题,最后释放内存。

    展开全部

    评论
    编辑
    预览

    报告相同问题?

    问题事件

    • 创建了问题 11月21日

    悬赏问题

    • ¥15 为什么树莓派5b显示禁止连接
    • ¥20 流量太费!寻找便宜的app音视频SDK或平替方案。
    • ¥15 kubeasz部署遇到问题
    • ¥15 GUIDE to App Designer Migration Tool for MATLAB
    • ¥50 第三代非支配排序遗传算法(NSGA-Ⅲ)和多目标粒子群优化算法(MOPSO)的实现
    • ¥20 plant simulation与python com接口实时数据交互
    • ¥15 有关汽车的MC9S12XS128单片机实验
    • ¥15 求c语言动态链表相关课程有偿,或能将这块知识点讲明白
    • ¥15 FLKT界面刷新异常
    • ¥15 物体双站RCS和其组成阵列后的双站RCS关系验证
    手机看
    程序员都在用的中文IT技术交流社区

    程序员都在用的中文IT技术交流社区

    专业的中文 IT 技术社区,与千万技术人共成长

    专业的中文 IT 技术社区,与千万技术人共成长

    关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

    关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

    客服 返回
    顶部