Проблема создания монет в ДП - получение неправильного ответа с помощью двумерной таблицы памятки - PullRequest
Новая
       71

Проблема создания монет в ДП - получение неправильного ответа с помощью двумерной таблицы памятки

2 голосов
/ 20 апреля 2020

Когда я передаю этот ввод, я получаю неправильный ответ

coin [] = {5,6}

Сумма (W) = 10

мой ответ = 1

Правильный ответ должен быть 2 т.е. {5,5} 

void coin_make(int W, vector<int> coin){

int n = coin.size();
int dp[n+1][W+1];


for(int i = 0; i <=W; i++){
    dp[0][i] = INT_MAX;
}

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

        if(coin[i-1] == j){
            dp[i][j]  = 1;
        }
        else if(coin[i-1] > j){
            dp[i][j] = dp[i-1][j];
        }
        else {
            dp[i][j] = min(dp[i-1][j], 
                        1 + dp[i][j-coin[i-1]]);
        }
    }
}
cout<<dp[n][W];}

1 Ответ

1 голос
/ 20 апреля 2020

Вы переполнены на dp[1][6], так как вы пытаетесь вычислить 1 + INT_MAX. Эта ошибка распространяется дальше, и, наконец, ответ не является правильным. Когда я запустил его на своей машине, я получил -2147483648. Вы должны использовать некоторую другую константу как «бесконечность» для предотвращения переполнения (например, 2e9 (или -1, но для этого потребуются некоторые дополнительные операторы if)). Тогда код будет хорошо работать на предоставленном вами тестовом примере.

...