关于派对的派对计划问题的问题 [英] An issue with party schedule problem on spoj

问题描述

我正试图解决SPOJ上的派对计划问题。不幸的是，我的代码总是标记为错误答案，问题的链接：

SPOJ.com - 问题派对 [ ^ ]

这是我的C ++代码，我使用矩阵来获得最大的乐趣，minPrice用于最低成本：

Hi, I was trying to solve the party schedule problem on SPOJ. Unfortunately my code is always signaled as "Wrong answer", the link of the problem:
SPOJ.com - Problem PARTY[^]
and Here is my C++ code, I used matrix for max fun, and minPrice for minimium cost:

#include <stdio.h>
#include <string.h>

using namespace std;

struct Party
{
    int fee;
    int fun;
    Party() {fee = 0; fun = 0;}
};

Party parties[101];
int matrix[101][501];
int minPrice[101][501];
int budget, num;

bool input();
void maxFun();

int main()
{
    for (int i = 0; i < 101; i++)
    {
        memset(matrix[i], 0, 501);
        memset(minPrice[i], 0, 501);
    }
    while(input())
    {
        maxFun();
        int fun = matrix[num][budget];
        int price = minPrice[num][budget];
        printf("%u %u\n", price, fun);
    }
}

bool input()
{
    scanf("%u %u", &budget, &num);
    if (!budget && ! num) return false;
    for (int i = 1; i <= num; i++) scanf("%u %u", &parties[i].fee, &parties[i].fun);
    return true;
}

void maxFun()
{
    int currentfun, updatedfun, updatedPrice, currentPrice;
    for (int i = 1; i <= num; i++)
    {
        for (int j = 1; j <= budget; j++)
        {
            currentfun  = matrix[i-1][j];
            updatedfun  =  parties[i].fun + matrix[i-1][j-parties[i].fee];

            currentPrice = minPrice[i-1][j];
            updatedPrice = parties[i].fee + minPrice[i-1][j-parties[i].fee];

            if (parties[i].fee <= j && updatedfun > currentfun)
            {
                matrix[i][j] = updatedfun;
                minPrice[i][j] = updatedPrice;
            }
            else if (parties[i].fee <= j && updatedfun == currentfun && updatedPrice < currentPrice)
            {
                matrix[i][j] = updatedfun;
                minPrice[i][j] = currentPrice;
            }
            else
            {
                matrix[i][j] = matrix[i-1][j];
                minPrice[i][j] = minPrice[i-1][j];
            }
        }
    }
}

那么错误在哪里？是算法吗？



谢谢大家，

Sam。



什么我试过了：



我试图安排各方提升，但当然它没有用..

So where is the mistake ? is it the algorithm ?

Thank you All,
Sam.

What I have tried:

I have tried to arrange the parties ascending, But of course it didn't work..

推荐答案

我认为现在是时候停止猜测你的代码在做什么了。是时候看到你的代码正在执行并确保它能达到预期的效果。



调试器是你的朋友。它会告诉你你的代码到底在做什么。

一步一步地执行，检查变量，你会发现它有一个停止做你期望的点。

掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]

http://docs.oracle .com / javase / 7 / docs / technotes / tools / windows / jdb.html [ ^ ]

https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html [ ^ ]



您的问题是探索各方的所有组合。另一种看待它的方法是探索二叉树。它也与反向跟踪有关。

对参与者列表进行排序只能是优化。

I think it is time for you to stop guessing what your code is doing. It is time to see your code executing and ensuring that it does what you expect.

The debugger is your friend. It will show you what your code is really doing.
Follow the execution step by step, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]

Your problem is about exploring all combinations of parties. Another way to see it is about exploring a binary tree. It is also related to back-tracking.
Sorting the list of parties can only be about optimization.

这篇关于关于派对的派对计划问题的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！