时间戳

首页 > 解决方案 > 你能解释一下问题出在哪里吗？[SPOj-练习]

c++ - 你能解释一下问题出在哪里吗？[SPOj-练习]

问题描述

我的意思是说老实说我找不到问题，而且这段代码似乎很容易写，我没有被接受。也许您可以帮助我并找到答案，因为老实说我不知道​​。我正在尝试在 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。这是不可能的。

标签： c++dynamic-programming

解决方案

在您的解决方案中，您只考虑每个重量硬币的最小价值，但如果这不增加确切的重量，您还必须使用其他硬币来匹配重量。这是练习变得有趣的时候。

当然，正如评论中所提到的，当你可以使用容器时，为什么会有内存泄漏？

推荐阅读