c++ - 派对日程-经典背包

Question

输入是可用预算、派对数量、每个派对的门票价格和派对的乐趣。任务是在可用预算和使用预算的情况下输出最大可能的乐趣。如果您可以在两个具有相同乐趣的聚会中进行选择，请选择更便宜的那个。 (这是一个 SPOJ problem 。)

我创建了两个数组:

• m[i][j] 是从 i 之前的各方获得的最大乐趣 预算 j
• p[i][j] py 得到最大值的最低价格。聚会的乐趣 最多 i 预算 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是完整的程序。

Answer 1

我没有按照你的逻辑检查了你的完整代码，但有一些错误的地方:

1. 您将函数中的 price 数组贴标为 price[parties]，它只允许 price[0..parties - 1]，但是你用完了 price[parties]，和 fun[] 一样；
2. while 的条件是 while(scanf("%u %u",&budget,&parties), budget != 0 && parties != 0),然而，即使在有效输入中，budget 也可以是 0，因此您的程序可能会比预期提前终止；
3. 您在函数内声明了 m[][] 和 p[][] 但没有初始化它，所以它会被垃圾值填满；
4. 您使用 printf("%u %u") 打印答案，但问题需要为每个输出换行，所以这里应该是 printf("%u %u\n").

在我改变了你程序中的这 4 个“错误”之后，它被接受了 :) 所以你的算法逻辑被批准了，但是一些“无关紧要”的东西阻止了你被接受。 不要小看这些“细节”，它们很重要!