Ագահ Ալգորիթմներ
Ագահ ալգորիթմները (Greedy Algorithms) լայնորեն կիրառվող մեթոդների հավաքածու են, որոնք վերջնական լուծումն աստիճանաբար կառուցում են՝ յուրաքանչյուր փուլում ընտրելով այն տարբերակը, որը տվյալ պահին ամենաակնհայտն է կամ օպտիմալը: Թեև ագահ ալգորիթմը սովորաբար հեշտ է հասկացվում, որոշ դեպքերում օպտիմալ էվրիստիկաները կարող են մի փոքր բարդ լինել և պետք է լավ հասկանալ, թե ինչպես է պետք կիրառել այդ էվրիստիկաները ամեն քայլին։
Առաջադրանք
Դուք ունեք մի պայուսակ (knapsack) և
n իր: Դուք ցանկանում եք տեղավորել հնարավորինս շատ իրեր, սակայն գիտեք, որ պայուսակը կպատռվի, եթե ընդհանուր քաշը գերազանցի t (threshold) շեմը: Պետք է պարզել, թե առավելագույնը քանի իր կարող եք տեղավորել պայուսակում այնպես, որ այն հնարավոր լինի տանել առանց վնասելու:Մուտք
Մուտքի առաջին տողում տրված է երկու ամբողջ թիվ
n (1 ≤ n ≤ ) և t (1 ≤ t ≤ ) - իրերի քանակը և պայուսակի տանելիք առավելագույն շեմը:Հաջորդ տողում տրված են
n ամբողջ թվեր (1 ≤ ≤ ), որոնք ներկայացնում են իրերի քաշերը:Ելք
Ծրագիրը պետք է տպի այն առավելագույն քանակի իրերի թիվը, որոնք կարող եք տանել:
Օրինակներ
Մուտք | Ելք |
7 10
4 1 2 5 8 7 1 | 4 |
Բացատրություն
Հնարավոր է պայուսակի մեջ տեղավորել, օրինակ,
1, 2, 5, 1, կամ 4, 1, 2, 1, կամ 1, 2, 7, 1 քաշերով իրերը: Բոլոր դեպքերում ընդհանուր 4 իր է տեղավորվում:Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB