Крок 1. Вибір черговий розглянутої точки х відповідно до лексикографічним порядком і з урахуванням впорядкування компонент x [j] по швидкості зміни. p align="justify"> Крок 2. Якщо фільтруюче обмеження сформовано, то - перевірка виконання його в точці х: якщо воно не виконується, то - перехід на крок 7. p align="justify"> Крок 3. Перевірка виконання в точці х чергового обмеження оптимізаційної задачі (у порядку їх ранжирування за ступенем активності): якщо воно не виконується, то - перехід на крок 7. p align="justify"> Крок 4. Якщо розглянуті не всі обмеження, то - на крок 3. p align="justify"> Крок 5. Обчислення цільової функції в черговий знайденої допустимої точці: z (x). p> Крок 6. Якщо фільтруюче обмеження ще не введено, то ввести його з правою частиною = z (x), зафіксувати = x. Якщо фільтруюче обмеження вже сформовано і виконується умова z (x) <, то перевизначити його праву частину (= z (x)) і зафіксувати = x. p> Крок 7. Якщо ще не всі точки розглянуті, то - на крок 1. p> Крок 8. Якщо (,) визначено, то це - оптимальне рішення, інакше D = Г†. br/>
5. Визначення даних
Програма підтримує рішення задачі з даними, що знаходяться у файлі input. txt. При запуску програми дані будуть лічені із зазначеного файлу. p align="justify"> Вихідні дані:
N - кількість предметів
MaxWeight - мах обсяг
W [i] - вага i-го предмета
P [i] - вартість i-го предмета
6. Вхідний файл
В
7. Вихідний файл
В
8. Тестова перевірка
Якщо вага предмета більше ніж обсяг сумки, (хоч його вартість і висока), то предмет не береться. У даному випадку це предмет 2 (вага 31, вартість 4000)
В
Якщо всі предмети більше ніж обсяг сумки, то жоден з предметів взятий не буде
В
9. Лістинг програми
program DP2;
{$ APPTYPE CONSOLE}
uses SysUtils; MaxW = 200; MaxN = 100; Value: array [0. MaxW, 0. MaxN] of integer; {масив значень (скільки можна набрати для 1. W терезів на 1. N предметів)}
Take: array [0. MaxW, 0. MaxN] of boolean; {масив значень брали предмет чи ні}
W, P: array [0. MaxN] of integer; {Масив ваг, масив цін}
i, N, Weight, MaxWeight: integer; Init; (input, 'input. txt'); (input); (N, MaxWeight); i: = 1 to N do readln (W [i], P [i]); (input);; Solve; (Take, sizeof (Take), false); {Обнуляємо рядок} (Value, sizeof (Value), 0); Weight: = 1 to MaxWeight do begin {вибираємо оптимум для ваги Weight} i: = 1 to N do {беремо предмети з 1 по N}
