Ҳиллаи фосилаи кушода ва пӯшида

Ҳилаи фосилаи кушода ва пӯшида

Муқаддима

Дар баъзе масъалаҳои DP, ба мо лозим мешавад гурӯҳҳо (ё интервалҳо) созем, ки арзиши ниҳоӣ аз элементи аввал ва охирин-и ҳар гурӯҳ вобаста аст. Барои ин як қолаби хеле муфид вуҷуд дорад: Ҳиллаи Интервали Кушода ва Пӯшида.

Идея содда аст:

• Мо элементҳоро бо тартиби сортшуда коркард мекунем.
• Мо иҷозат медиҳем, ки гурӯҳҳо муваққатан кушода бошанд.
• Баъдтар мо онҳоро мепӯшем, вақте ки нӯги рости онҳо муайян мешавад.

Ин ба мо имкон медиҳад, ки пайгирии ошкори ҳамаи нуқтаҳои охири интервалҳоро пешгирӣ кунем.

Баёни масъала

Ба мо $n$ барномасоз дода шудааст, ки сатҳҳои маҳораташон аз $0$ то $100$ мебошанд. Мо мехоҳем онҳоро ба дастаҳо тақсим кунем, то ки ҷаримаи умумӣ аз $x$ зиёд набошад.

Барои як даста, ҷарима = фарқияти байни баландтарин ва пасттарин маҳора.

Ҷаримаи умумӣ = суммаи ҷаримаҳои ҳамаи дастаҳо.

Шумораи роҳҳои дурусти ташкил кардани дастаҳоро ҳисоб кунед.

Идеяи асосӣ

Барномасозонро аз рӯи маҳораташон сорт кунед.
Ҳоло ҳар даста ба як қисмати пайдарпай дар тартиби сортшуда табдил меёбад.

Ҳангоми аз чап ба рост гузаштани барномасозон:

• баъзе дастаҳо аллакай анҷом ёфтаанд
• баъзе дастаҳо ҳанӯз кушода ҳастанд (мо минимумро интихоб кардем, аммо ҳанӯз максимумро не)