Динамическое программирование MPILOT

Question

Я пытаюсь решить проблему на spoj (MPILOT).

Я понял, что это динамическая проблема программирования, и я тоже пробовал ее, но это дало мне неправильный ответ. мой подход похож на получение разницы в зарплате пилота и помощника и сортировку в порядке убывания, а затем для 0 - N/2 добавить как assistant и для N/2+1 - N добавить как pilot и вывести sum. но проблема идет с возрастным состоянием, что пилот должен быть старше помощника.

Вот мой код

#include <iostream> 
#include <vector> 
#include <algorithm> 
#define lint long long 

using namespace std; 

struct pilot { 
lint pilotsal; 
lint assistantsal; 
lint diff; 
}; 

bool compare (pilot p1, pilot p2) 
{ 
return (p1.diff > p2.diff); 
} 

int main() 
{ 
lint c,n,i; 
lint sum=0,max=0; 
cin >> n; 
vector <pilot> pilots(n); 
for(i=0;i<n;i++) 
{ 
    cin >> pilots[i].pilotsal >> pilots[i].assistantsal; 
    pilots[i].diff= pilots[i].pilotsal-pilots[i].assistantsal; 
} 
sum = max = pilots[0].assistantsal; 
sort(pilots.begin()+1,pilots.end(),compare); 
for(i=1;i<=n/2-1;i++) 
{ 
    sum+=pilots[i].assistantsal; 
} 

for(i=n/2;i<n;i++) 
{ 
    sum+=pilots[i].pilotsal; 
} 
    cout << sum << endl; 
    return 0; 
} 

пожалуйста, дайте мне подсказку. как проверить возрастное состояние проблемы.

Answer 1

После часа, пытаясь решить эту проблему с помощью «динамического программирования», я пришел к выводу, что это не так, но проблема еще не решена. Многие жадные идеи пришли мне на ум, но жадность в большинстве случаев не очень хороша.

В конце концов, я не мог решить эту проблему, но поскольку эта проблема интересна я искать решение, и вот что я понимаю решения:

Пилоты сортируются в порядке возрастания:

• самый первый пилот должен быть помощником
• самый последний пилот должен быть капитаном

Самое худшее решение, когда р всех пилотов (капитанов и помощников) в качестве капитанов. Это будет наше первое решение, и мы постараемся уменьшить эту сумму до минимума.

экономия мы можем получить от поворота капитана до ассистента Pilot.CaptainWage - Pilot.AssistantWage.

Проблема становится легкой, потому что требуется минимальная оплата, а не сама группировка.

1. Set the first pilot as assistant 
2. Insert each pilot in a list from the second to the last, and for every 2 new elements in the list 
    // One pilot can be turned to an assistant only if remains at least another older pilot 
    2.1 Select the pilot who contribute with the maximum saving so far 
    2.2 Rest the saving of the previous step to our original solution 
    2.3 Remove the pilot from the list 
3. Print our new solution 

Примечание: Вам нужны эффективная структура данных для получения пилотов с максимальной экономией в быстром способе, может быть heap.

Посмотрите, сможете ли вы решить проблему. Я не размещаю ссылку на фактическое решение, потому что лучше, если вы сначала попробуете это самостоятельно :).