Расписание вечеринок — классический рюкзак

Question

Расписание вечеринок — классический рюкзак

Вводится доступный бюджет, количество вечеринок, цена билета каждой вечеринки и сумма веселья на вечеринке. Задача состоит в том, чтобы вывести максимально возможное удовольствие с имеющимся бюджетом и использованным бюджетом. Если вы можете выбрать между двумя вечеринками с одинаковым весельем, выберите более дешевый. (Это SPOJ проблема.)

Я создал два массива:

m[i][j] это максимальное удовольствие получить от всех сторон до меня с
бюджет j
p[i][j] минимальная цена на ру, чтобы получить макс. веселье с вечеринок
до меня с бюджетом j

Затем для каждого i до #parties и для каждого 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];
}
}
}

Для любого тестового случая, который я обнаружил (я могу поделиться некоторыми при необходимости), этот алгоритм выдает тот же ответ, что и алгоритмы, утвержденные онлайн-судьей. Однако этот не одобрен.

Что не так с алгоритмом?

Вот это полная программа

1

algorithm c++knapsack-problem

Решение

Другие решения

Источник

Accepted Answer

Я проверил ваш полный код, не разбираясь с логикой, но были некоторые ошибки:

Вы удалили свою 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 «ошибки» в вашей программе, она была принята 🙂 Итак, ваша логика алгоритма одобрена, но некоторые «неуместные» вещи мешают вам быть принятыми. Не смотрите свысока на эти «детали», они действительно имеют значение!

2