Размен монет: найдите количество способов воспроизвести заданную сумму.

Если задано значение N, если мы хотим внести сдачу на N центов и у нас есть бесконечный запас каждой из монет номиналом S = {S1, S2, .. , Sm}, сколькими способами мы можем внести сдачу? Порядок монет значения не имеет. Например, для N = 4 и S = ​​{1,2,3} имеется четыре решения: {1,1,1,1},{1,1,2},{2,2},{1, 3}. Таким образом, на выходе должно быть 4. Для N = 10 и S = ​​{2, 5, 3, 6} есть пять решений: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} и {5,5}. Таким образом, на выходе должно быть 5.

Ссылка на вопрос: https://www.geeksforgeeks.org/coin-change-dp-7/

Я наткнулся на все решения.

Я использовал матричный метод, чтобы найти решение для этого:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#define ll long long
//Author: Nilargha Roy (neel13)
using namespace std;
int coinchangeways(int arr[],int n,int sum)
{

        int dp[n+1][sum+1];
        memset(dp,-1,sizeof(dp));


        for(int j=1;j<n;j++)
        {
            dp[0][j]=0;
        }
        for(int i=0;i<n;i++)
        {
            dp[i][0]=1;
        }



    for(int i=1;i<n+1;i++)
    {
        for(int j=1;j<sum+1;j++)
        {

            if(arr[i-1] <= j)
                dp[i][j]=dp[i][j-arr[i-1]] + dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j];

        }
    }

    return dp[n][sum];

}

int main() 
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);

#ifdef __APPLE__
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int sum; cin>>sum;
    cout<<coinchangeways(arr,n,sum);
}

Однако, когда я ввожу массив = {1,2,3} и SUM = 5 в качестве входных данных, вывод должен быть: 5, а я получаю 1. Может ли кто-нибудь определить логическую ошибку в моем коде?


c++ algorithm dynamic-programming coin-change
person Nilargha Roy    schedule 19.06.2020    source источник
comment
Вам придется попытаться найти логическую ошибку в вашем коде, используя отладчик, для этого он и существует. Эти бессмысленные сайты онлайн-конкурсов обычно создают код, который трудно прочитать другим людям, и помогают вам с ним, так что вы здесь сами по себе. Он полон бесполезных макросов и нестандартного C++, как здесь. Вы обнаружите, что будет полезно провести больше времени с качественным учебником C++, изучая основные концепции C++, такие как естественное индексирование массива на основе 0. Показанный код пытается использовать неестественную индексацию массива на основе 1, что еще больше затрудняет чтение и понимание его логики.   -  person Sam Varshavchik    schedule 19.06.2020
comment
мой новый любимый кульминационный момент: соревновательное кодирование для изучения языка похоже на поход на панк-концерт, чтобы подготовиться к конкурсу танцев вальса. Плохо то, что они создают впечатление, будто программирование — это написание правильного кода. Это не. Крошечная часть программирования — это написание кода, а огромная — отладка и тестирование. Вы написали немного кода, теперь вам нужно сделать и все остальное   -  person 463035818_is_not_a_number    schedule 19.06.2020
comment
@ idclev463035818 извините, что разорвал ваш пузырь, но я не использовал CP в качестве средства для изучения какого-либо языка, я просто хотел помочь с моим решением. Спасибо. Боже скорости.   -  person Nilargha Roy    schedule 19.06.2020
comment
Попробуйте распечатать первую строку вашего массива после его инициализации.   -  person Paul Hankin    schedule 19.06.2020
comment
@PaulHankin Я сделал. Все хорошо.   -  person Nilargha Roy    schedule 19.06.2020
comment
извините, что разорвал ваш пузырь, но использование отладчика является важным навыком, и, похоже, вам нужно наверстать упущенное.   -  person 463035818_is_not_a_number    schedule 19.06.2020
comment
Извините за мой предыдущий ошибочный комментарий. Кажется, что -1 распространяется через массив DP. Вы можете попытаться инициализировать его значением 0, а не -1.   -  person Damien    schedule 19.06.2020
comment
Вы в курсе, что для этой задачи достаточно 1d-массива?   -  person MBo    schedule 19.06.2020
comment
@MBo Эй, чувак, можешь объяснить, как?   -  person Nilargha Roy    schedule 19.06.2020
comment
Я добавил ответ с кодом массива 1d   -  person MBo    schedule 19.06.2020

Ответы (2)


arrow_upward
1
arrow_downward

когда вы запускаете свою функцию после всего цикла for. у вас будет DP, показанный ниже.

 1   0   0  -1  -1  -1

 1   1   1   0  -1  -2

 1   1   2   1   1  -1

 -1  1   2   0   2   1

dp[3][5] = 1, поэтому вы получаете 1.

person Nilesh Solanki    schedule 19.06.2020
comment
Я понимаю, что инициализировал первый цикл до n вместо суммы. Большое спасибо. Удачи. - person Nilargha Roy; 19.06.2020
comment
вы также можете инициализировать свой dp с помощью 0 и удалить первые два цикла for и просто написать dp[0][0] =1. - person Nilesh Solanki; 19.06.2020

arrow_upward
2
arrow_downward

Версия, использующая массив 1d:

int coinchangeways(int arr[], int n, int sum)
{
    int dp[sum+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;

    for (int i = 0; i < n; i++)
    {
        for (int j = arr[i]; j <= sum; j++)
        {
                dp[j] += dp[j - arr[i]];
        }
    }

    return dp[sum];
}
person MBo    schedule 19.06.2020