Можете ли вы объяснить мне, где проблема? [SPOJ-упражнения]

Question

Я имею в виду, что честно не могу найти проблему, и этот код кажется очень простым для написания, и меня не принимают. Может быть, Вы можете помочь мне и найти ответ, если честно, я понятия не имею. Я пытаюсь выполнить это упражнение на SPOJ: https://www.spoj.com/problems/PIGBANK/. Я буду очень благодарен за любое объяснение того, что не так в моем подходе.

#include <iostream>

using namespace std;

void piggyBank(int, int);
int sumAll(int *,int, int);


/* SUMMARY

    We need to find the smallest value available in the piggy bank

*/

int main()
{
    int t = 0, e = 0, f = 0;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> e >> f;
        piggyBank(e, f);
    }
    return 0;
}

void piggyBank(int weightEmpty, int weightFull)
{
    int coinsAmount = 0, *coinValue, *coinWeight, totalWorth = 0, remainingWeight = weightFull - weightEmpty, smallestValPos = 0;
    cin >> coinsAmount;
    coinValue = new int[coinsAmount];
    coinWeight = new int[coinsAmount];
    // getting all the coins and weights in the piggy bank
    for (int i = 0; i < coinsAmount; i++)
    {
        cin >> coinValue[i] >> coinWeight[i];
        if ((remainingWeight / coinWeight[smallestValPos] > remainingWeight / coinWeight[i]) && (remainingWeight % coinWeight[i] == 0)) smallestValPos = i;
    }
    // we need to check how many coinValue[smallestValPos] are there inside piggy bank
    if(remainingWeight%coinWeight[smallestValPos] == 0)totalWorth = remainingWeight / coinWeight[smallestValPos] * coinValue[smallestValPos];
    // output according to the excercise's constraints
    if (totalWorth == 0) cout << "This is impossible.\n";// << endl;
    else cout << "The minimum amount of money in the piggy-bank is " << totalWorth << ".\n"; //<< endl;
}

int sumAll(int *tab,int start, int end)
{
    int sum = 0;
    for (int i = start; i < end; i++)
    {
        sum += tab[i];
    }
    return sum;
}

Пример ввода от SPOJ:

3 10 110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4

Пример вывода из SPOJ:

Минимальная сумма денег в копилке составляет 60. Минимальная сумма денег в копилке составляет 100 . Это невозможно.

Answer 1

В вашем решении вы принимаете во внимание только наименьшую ценность на весовую монету, но если это не увеличивает точный вес, вы также должны использовать другие монеты, чтобы соответствовать весу. Это когда упражнение становится интересным.

И, конечно, как уже упоминалось в комментариях, почему возникают утечки памяти, когда вы можете использовать контейнеры?

Answer 2

Учитывая вес W и монеты с весом C_i и значением V_i, у вас есть следующее отношение повторения:

minValue (W) = min {V_1 + minValue (W-C_1), V_2 + minValue (W-C_2), ...}
minValue (0) = 0

Вам необходимо учитывать, что некоторые веса недоступны (ie W = 3, когда у вас есть только монеты с весом 5 и 10), но в остальном это довольно просто.

Вышеприведенное соотношение очень хорошо подходит для динамического программирования c: просто начните вычислять с W = 0, пока не достигнете целевого веса.