使用允许重复的动态编程背包的硬币找零程序 [英] coin change program using dynamic programming knapsack with repetitions allowed

问题描述

我编写了以下代码来实现硬币找零问题:给您n种类型的硬币面额，值v(1)<v(2)<...<v(n)(所有整数).假设v(1)= 1，则您始终可以对任何金额的C进行找零.给出一种算法，该算法可以用尽可能少的硬币对金额C进行找零.

I have written the below code to implement the coin change problem: you are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible.

我通过将每个硬币的所有值都设置为-1来修改背包允许重复的问题.然后，程序应返回最大值，以使所需硬币(面额)的重量加起来成为大小变量(所需的零钱).我无法弄清楚哪里出了问题.我应该得到-2的答案，这意味着我需要两个硬币，但我得到-1作为答案.代码:

I modified the knapsack with repetitions allowed problem by setting all the values of each coin to -1. The program should then return the maximum value such that the weight of the required coins(denominations) add up to the size variable(required change). I cannot figure where i have went wrong. I should be getting an answer of -2 implying i need two coins but i'm getting -1 as the answer. Code:

#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;
}

我要去哪里错了，我该如何解决?

Where am i going wrong and how can i fix this?

推荐答案

这很简单，因为 -1>-2 ，并且您在每个级别的2个选择之间取最大值.

It is simple because, -1 > -2 and you are taking the maximum between the 2 choices at every level.

我已经推行了一个解决方案，其中将值视为正值，如果有一些您不理解的问题，我也对代码进行了微小的更改.

EDIT : I have impelmented a solution in which values are taken as positive, also i have made minor changes to the code, if there is something that you do not understand feel free to ask.

#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

Link to solution on Ideone : http://ideone.com/TNycZo

在这里，我将无穷大作为一个大整数来查找最小值，如果答案是无穷大，则意味着不可能创建这样的面额.

Here i have taken infinity as a large integer, to find minimum values, if the answer is infinity that means it is not possible to create such a denomination.

这篇关于使用允许重复的动态编程背包的硬币找零程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！