c++ - 宴会时间表-经典背包

输入的内容包括可用预算，聚会数量，每个聚会的门票价格以及聚会上的乐趣。任务是输出可用预算和所用预算的最大乐趣。如果您可以在两个有趣的派对之间进行选择，请选择便宜的一个。 (这是一个SPOJ problem。)

我创建了两个数组:

m[i][j]是最大的乐趣，可以让各方与我一起
预算j

p[i][j]到py的最低价格以获得最高价格。来自聚会的乐趣
由预算j

决定

然后，对于不超过#parties的每个i和不超过预算的每个j，我按以下方式计算m[i][j]和p[i][j]的值:

for(T i = 1; i <= parties; i++) {
    for(T j = 0; j <= budget; j++) {
        //We get more fun by attending party i
        if(price[i] <= j && m[i-1][j-price[i]] + fun[i] > m[i-1][j]) {
            m[i][j] = m[i-1][j-price[i]] + fun[i];
            p[i][j] = p[i-1][j-price[i]] + price[i];
        //We get same fun by attending i, but more cheaply
        } else if(price[i] <= j && m[i-1][j-price[i]] + fun[i] == m[i-1][j] && p[i-1][j-price[i]] + price[i] < p[i-1][j]) {
            m[i][j] = m[i-1][j-price[i]] + fun[i];
            p[i][j] = p[i-1][j-price[i]] + price[i];
        //We can't visit the party
        } else {
            m[i][j] = m[i-1][j];
            p[i][j] = p[i-1][j];
        }
    }
}

对于我发现的任何测试用例(如果需要，我可以共享一些用例)，该算法输出的答案与在线法官认可的算法相同。但是，这一批准未被批准。

该算法有什么问题？

Here是完整的程序。

最佳答案

我没有检查逻辑就检查了完整的代码，但是有一些必须注意的地方:

您将函数中的price数组除为price[parties]，只允许price[0..parties - 1]，但您用尽了price[parties]，与fun[]相同；

您的while的条件是while(scanf("%u %u",&budget,&parties), budget != 0 && parties != 0)，但是即使在有效输入中，budget也可以是0，因此您的程序可能比预期的更早终止。

您在函数内部声明了m[][]和p[][]，但未对其进行初始化，因此将被垃圾值填满。

您可以使用printf("%u %u")打印答案，但是问题是每个输出都需要换一行，因此这里应该是printf("%u %u\n")。

在我更改了程序中的这4个“错误”之后，它就被接受了:)因此，您的算法逻辑得到批准，但是某些“不相关”的事情阻止了您被接受。 不要小看这些“细节”，它们确实很重要!

关于c++ - 宴会时间表-经典背包，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25596953/