使用动态规划背包问题解法实现硬币找零程序（允许重复）

Question

使用动态规划背包问题解法实现硬币找零程序（允许重复）

3

我编写了以下代码来实现找零问题：你会得到n种货币面额，它们的价值为v(1) < v(2) < ... < v(n)（所有整数）。假设v(1) = 1，因此您可以始终找零任何金额C。给出一种算法，以尽可能少的硬币找零金额C。

我通过将每个硬币的所有值设置为-1来修改了允许重复的背包问题。然后，程序应返回最大值，使所需硬币（面额）的重量相加等于size变量（所需找零）。我无法确定哪里错了。我应该得到一个-2的答案，意味着我需要两枚硬币，但我得到的答案是-1。代码：

#include <stdio.h>
#define max(a,b) (a > b ? a : b)

int matrix[100][100] = {0};

int knapsack(int index, int size, int weights[],int values[]){
    int take,dontTake;

    take = dontTake = 0;

    if (matrix[index][size]!=0)
        return matrix[index][size];

    if (index==0){
        if (weights[0]<=size){
            matrix[index][size] = values[0];
            return values[0];
        }
        else{
            matrix[index][size] = 0;
            return 0;
        }
    }

    if (weights[index]<=size) 
        take = values[index] + knapsack(index, size-weights[index], weights, values); //knapsack(index) and not //knapsack(index-1) 

    dontTake = knapsack(index-1, size, weights, values);

    matrix[index][size] = max (take, dontTake);

    return matrix[index][size];

}

int main(){
    int nItems = 4;
    int knapsackSize = 10;
    int weights[4] = {5,4,6,3};
    int values[4] = {-1,-1,-1,-1};

    printf("Max value = %dn",knapsack(nItems-1,knapsackSize,weights,values));

    return 0;
}

我哪里做错了，该怎么解决？

- RaviTej310

1

除此之外，你应该在调试器中运行程序，并逐行步进代码，以查看何时以及在哪里它没有执行预期的操作。像这样调试程序是一项艰苦的工作，但也是所有程序员必须做和知道如何做的事情。 - Some programmer dude

我已经尝试了很多次，但仍然卡住了。 - RaviTej310

你需要尝试缩小问题范围。如果你理解算法的工作原理，你应该能够确定在执行过程中出现了意外情况的具体位置。如果你不理解算法的工作原理，那么你需要具体描述你不理解的内容。 - Vaughn Cato

你是如何使用矩阵的（第一个索引是什么，第二个索引是什么？），weights代表什么，values又代表什么？ - MicroVirus

矩阵基本上是用来存储已计算出的值的。索引是我们仍然可以选择的物品数量。大小表示未使用的重量或尚未核算的更改金额。权重数组给出每个硬币的面值。价值数组为每种硬币赋值，在这种情况下，每个硬币的价值为-1，因为我们取哪些硬币并不重要。重要的是硬币的数量。 - RaviTej310

如果您想要同一种类型的多个硬币，您需要在递归解决方案中嵌套一个循环来迭代硬币的数量，稍后我会尝试提供一个解决方案。 - uSeemSurprised

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- uSeemSurprised · Accepted Answer

这很简单，因为在每个层级上，您选择的两个选项中取最大值，所以-1 > -2。编辑：我已经实现了一个解决方案，其中数值被视为正数，还对代码进行了微小的更改，如果有什么不明白的地方，请随时提问。

#include <stdio.h>
#define min(a,b) (a < b ? a : b)
#define INF 10000000

int matrix[100][100] = {0};

int knapsack(int index, int size, int weights[],int values[]){
    int take = INF;

    if (index == -1){
        if(size == 0) return 0;
        else return INF;
    }

    if (matrix[index][size]!=-1)
        return matrix[index][size];

    for(int itemcount = 0;(itemcount * weights[index]) <= size;itemcount++){
        if ((weights[index] * itemcount) <= size) 
            take = min(take, (values[index] * itemcount) + knapsack(index - 1, size - (itemcount * weights[index]), weights, values)); //knapsack(index) and not //knapsack(index-1) 
    }

    matrix[index][size] = take;

    return matrix[index][size];

}

int main(){
    int nItems = 4;
    int knapsackSize = 10;
    int weights[4] = {5,4,6,3};
    int values[4] = {1,1,1,1};
    for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) matrix[i][j] = -1;

    printf("Min value = %d\n",knapsack(nItems-1,knapsackSize,weights,values));

    return 0;
}

在Ideone上的解决方案链接：http://ideone.com/TNycZo

在这里，我将无限大定义为一个大整数，以找到最小值，如果答案是无限大，则表示无法创建这样的面额。