在 c 中使用动态规划进行更改时出错

Question

我已经尝试了很多次，但仍然无法在下面的代码中找到错误，它正在使用动态编程进行更改问题，需要帮助来消除错误的输出，如果可能，请告诉我这是否是解决此问题的理想方法动态规划：

代码

    #include<stdio.h>
    int min(int a , int b)
    {
        if(a>b)
        {
            return b;
        }
        else if (b>a)
        {
            return a;
        }
    }
    void making_change(int n,int c,int value[])
    {
        int i,j,m[n][c];
        for(j=1;j<=c;j++)
        {
            m[0][j]=9999;
        }
        for(i=0;i<=n;i++)
        {
            m[i][0]=0;
        }
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= c; j++)
            {
                if (j-value[i-1]<0)
                {
                    m[i][j]=m[i-1][j];
                }
                else
                {
                    m[i][j]=min(m[i-1][j],1+m[i][j-value[i-1]]);
                }
            }
        }
        printf("The number of required coins are : %d",m[n][c]);
    }
    void main()
    {
        int i,c,n;
        printf("Enter the number of different coins : ");
        scanf("%d",&n);
        int value[n];
        printf("Enter the total cost : ");
        scanf("%d",&c);
        printf("********************Enter the values of different coins******************** \n");
        for(i=0;i<n;i++)
        {
            printf("Enter the value of coin %d : ",i+1);
            scanf("%d",&value[i]);
        }
        making_change(n,c,value);
    }

**错误的输出是：** 输入不同硬币的数量：3 输入总成本：8 输入不同币值 输入硬币面值 1 : 1 输入硬币 2 : 4 的面值 输入硬币的面值 3 : 6 所需金币数量为：0

在正确的情况下，硬币的数量应该是 2，即两枚价值 4 的硬币。在查找 m(1,1) 的值时出错，它是 999，但应该是 1。

正确的输出是： 输入不同硬币的数量：3 输入总成本：8 输入不同币值 输入硬币面值 1 : 1 输入硬币 2 : 4 的面值 输入硬币的面值 3 : 6 所需金币数量为：2

Answer 1

我可以看到您的代码有几个问题：

1. 您的

   min

   函数无法处理两个值相等的情况。您应该为这种情况添加退货。
2. 矩阵

   m

   的维度定义不正确。尺寸应为

   [n+1][c+1]

   而不是

   [n][c]

   。这是因为您正在考虑 0 到

   n

   硬币和 0 到

   c

   成本（含）。

3. m[0][j]=9999;

   的初始化应该从

   j=0

   开始，而不是从

   j=1

   开始。这是因为即使成本为 0，您也需要 0 个硬币。

让我们纠正这些问题：

#include<stdio.h>

int min(int a , int b) {
    if(a <= b) {
        return a;
    } else {
        return b;
    }
}

void making_change(int n, int c, int value[]) {
    int i, j;
    int m[n+1][c+1];
    
    for(j=0; j<=c; j++) {
        m[0][j]=9999;
    }
    m[0][0] = 0;
    
    for(i=1; i<=n; i++) {
        m[i][0]=0;
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= c; j++) {
            if (j-value[i-1] < 0) {
                m[i][j] = m[i-1][j];
            } else {
                m[i][j] = min(m[i-1][j], 1+m[i][j-value[i-1]]);
            }
        }
    }
    printf("The number of required coins are : %d", m[n][c]);
}

void main() {
    int i, c, n;
    printf("Enter the number of different coins : ");
    scanf("%d", &n);
    int value[n];
    printf("Enter the total cost : ");
    scanf("%d", &c);
    printf("********************Enter the values of different coins******************** \n");
    for(i=0; i<n; i++) {
        printf("Enter the value of coin %d : ", i+1);
        scanf("%d", &value[i]);
    }
    making_change(n, c, value);
}

现在，这段代码应该为给定的输入提供正确的输出。

---