Расписание партии - классический рюкзак

Question

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

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

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

Тогда для каждого г до #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]; 
     } 
    } 
} 

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

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

Here - полная программа.

Answer 1

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

1. Вы decalred вашего 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 «ошибки» в вашей программе, он принимается :) Итак, ваша логика алгоритма одобрена, но некоторые «неуместные» вещи мешают вам принять. Не смотрите вниз на эти «детали», они СЧИТАЮТ!