Knapsack խնդիրը-ը կարևոր և հայտնի խնդիր է, որը տրվել է տարբեր մրցակցային ծրագրավորման մարտահրավերների, ինչպես նաև MNC-ի կոդավորման փուլի որոշ մարտահրավերների ժամանակ: Խնդիրը հետեւյալն է
Այսօր եկեք ձեզ գող համարենք. Դուք ունեք պայուսակ, որն ունի որոշակի առավելագույն տարողություն
Եթե տարողությունից ավելի տարր ընտրեք, ձեր պայուսակը կհասունանա: Յուրաքանչյուր տարր ունի տարբեր գնահատականներ, այնպես որ դուք պետք է համոզվեք, որ հնարավորինս շատ իրեր եք ընտրել, որոնք ունեն առավելագույն արժեք:
Դուք պարզապես գող չեք, այլ ագահ գող եք, ուստի ձեր ջանքերը թափում եք հարստանալու համար:
Քայլեր
Ալգորիթմ
Մեթոդ-1
1. Այս մեթոդը պարզ ուսապարկի մեթոդ է
2. Հարցին պատասխանելու համար օգտագործում է ռեկուրսիվ զանգ:
3. Այս մեթոդում կան երկու զանգված՝ արժեքը [] և քաշը []:
4. Դիտարկենք զանգվածների բոլոր ենթաբազմությունները և այնուհետև հաշվարկենք այդ ենթաբազմությունների ընդհանուր քաշը և արժեքը:
5. Այս ենթաբազմություններից վերցրեք առավելագույն արժեքը:
6. Այս վիրահատությունը կատարելիս երկու դեպք կա.
ես. Ենթաբազմությունը ներառելու համար:
ii. Այն ենթաբազմությունից բացառելու համար։
7. Արժեքներից ստացվող ելքը առավելագույն արժեքն է
ես. Առավելագույն արժեքը n-1 միավորից և W քաշից (բացառությամբ n-րդ կետի):
ii. Ներառյալ n-րդ տարրի արժեքը և n-1 կետի և W առավելագույն արժեքը և դրանից հանելով n-րդ տարրի կշիռը (ներառյալ n-րդ կետը):
8. Եթե n-րդ տարրի կշիռն արդեն մեծ է, քան W-ը, ապա կա միայն մեկ հնարավորություն, որը ներառում է ենթաբազմությունը:
Մեթոդ 2:
1.գտնել արժեքը միավորի քաշի համար
2. Դասավորել ըստ արժեքի/քաշի նվազման կարգով: Առավելագույն արժեք ստանալու համար ընտրեք տարրեր, որոնք ունեն առավելագույն արժեք միավորի քաշի արժեքի համար
3. Այժմ ձեր պարկը լցրեք առավելագույն կշիռներով, եթե քաշը չափազանց մեծ է, ապա ներառեք մնացած կշիռը, որը կարող է լցնել պարկը մինչև իր առավելագույն տարողությունը (մ), և արժեքը կարելի է գտնել՝ բազմապատկելով մեկ միավորի քաշի արժեքը մինչև թիվ: այն քանակությունը, որը վերցրել ենք պարկը լցնելու համար (մ)
Ավելի շատ նման հուզիչ խնդիրների համար սպասեք!!!
