Получение проблем в моей реализации рюкзака (PARTY)
Я пытался сделать этот простой вопрос из спой сегодня, и это проблема ранца, я реализовал это следующим образом:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
while(true)
{
int budget, t;
scanf("%d%d", &budget, &t);
if(budget == 0 && t == 0)
break;
int cost[t], fun[t];
vector<pair<double, int> > knap;
for(int i = 0;i < t;i++)
{
scanf("%d%d", &cost[i], &fun[i]);
knap.push_back(pair<double, int>(double(fun[i])/double(cost[i]), i));
}
sort(knap.rbegin(), knap.rend());
int totfun = 0, bud = budget;
for(int i = 0;i < int(knap.size());i++)
{
if(bud - cost[knap[i].second] >= 0)
{
bud -= cost[knap[i].second];
totfun += fun[knap[i].second];
}
}
printf("%d %d\n", budget-bud, totfun);
}
}
Но это решение дают WA (неправильный ответ). Я перепробовал все тестовые примеры на собственном форуме spoj, и мой код, кажется, прошел их все. Может ли кто-нибудь мне помочь, это одна из первых проблем с DP, которую я пробовал …
Решение
Код в вопросе делает не реализовать точное решение с помощью Динамическое программирование, но жадный алгоритм, который в общем случае не вычисляет оптимальное решение. Однако задача по ссылке в вопросе, по-видимому, требует генерации оптимального решения.
Субоптимальность жадного алгоритма может быть доказана при рассмотрении следующего случая.
Item 1: Function 6, Cost 4 (Ratio 18/12)
Item 2: Function 4, Cost 3 (Ratio 16/12)
Item 3: Function 3, Cost 3 (Ratio 12/12)
Capacity: 6
Жадный алгоритм выбрал бы Item 1, приносящий прибыль 6, Однако выбирая Item2 а также Item3 приносит общую прибыль 7,
Другие решения