Knapsack мәселесінің нұсқасы: Java-да «Бөлінетін жиынтық сомасы» мәселесін қалай шешуге болады

Жаңарту: Сіз динамикалық бағдарламалау шешімінің ғарыштық күрделілігін оңтайландыру туралы ақпаратты мына мақалада таба аласыз.

Бұған дейін мен Knapsack (KP) мәселесін динамикалық бағдарламалау арқылы шешу туралы жаздым. Ол туралы мына жерден оқи аласыз.

Бүгін мен КП нұсқасын талқылағым келеді: бөлу мәселесі ішкі жиынтыққа тең. Мен бұл мәселені бірінші рет Leetcode-да көрдім - KP туралы білуге ​​және ол туралы жазуға себеп болды.

Мәселе мынада (мысалсыз ішінара шығарылады):

Тек оң бүтін сандарды қамтитын бос емес массив үшін элементтердің қосындысы екі ішкі жиында бірдей болатындай массивті екі ішкі бөлікке бөлуге болатынын анықтау керек.

Шектемелер мен мысалдармен проблеманың толық сипаттамасын Leetcode есебінде табуға болады.

Динамикалық бағдарламалау

КП сияқты біз мұны динамикалық бағдарламалау арқылы шешеміз. Бұл КП өзгермелі болғандықтан, логика мен әдіс-тәсілдер көбіне ұқсас.

Шешімі

Біз шешімімізді логикалық мәнді қайтаратын әдіске орналастырамыз - егер жиым тең жиындарға бөлінуі мүмкін болса, шындық, егер дұрыс болмаса.

1-қадам: тақ тақтадан қорғану

Егер массивтегі барлық сандар тақ сандарға көбейтілсе, біз жалған қайтара аламыз. Егер массив жұп сан болса ғана біз жалғастырамыз.

2-қадам: кесте құру

Келесі кестені жасаймыз.

Кесте жолдары қарастырылатын массив элементтерінің санын, ал кесте бағандары біз алу керек соманы көрсетеді. Кестелік мәндер жиынтықты (бағанды) массив элементтерінің (жолдың) көмегімен анықтауға болатындығын көрсететін жай логикалық мәндер.

Атап айтқанда, i жолы 0-ден (i-1) дейінгі индекстерден тұратын массив элементтерінің жиынтығын білдіреді. 1-ден басталудың себебі 0-жол бос элементтер жиынтығын білдіреді. Сонымен, 1-ші қатар бірінші массивтің элементіне (индекс 0), ал екінші екі массивтің екі элементіне (индекстер 0–1) және т.с.с. барлығында 0 санын қосқанда n + 1 жолдар құрамыз.

Біз массивтің жартысының дәл жартысын қорытындылай алатынымызды білгіміз келеді. Сондықтан бізде 0, оның ішінде totalSum / 2 + 1 бағандарын құру керек.

3-қадам: кестені алдын-ала толтыру

Біз бірден кестедегі негізгі регистрлер үшін жазбаларды толтырудан бастай аламыз - 0-жол мен 0-баған.

Бірінші жолда әр жазба, бірінші жолды қоспағанда, қате көрсетілуі керек. Есіңізде болсын, бірінші жол бос жиынтығын білдіреді. Әрине, біз мақсаттық соманы анықтай алмаймыз - баған нөмірі - 0-ден басқа.

Бірінші бағанда әр жазба шын болуы керек. Біз жұмыс істеуіміз керек элементтердің санына қарамастан, 0-ге мақсатқа жете аламыз.

4-қадам: кесте құру (мәселенің өзегі)

Кестеге i және j бағанындағы жазба шынайы (қол жетімді), егер келесі үш шарттың біреуі орындалса:

  1. I-1 және j бағанындағы жазба дұрыс. Жол нөмірі нені білдіретінін есіңізде сақтаңыз. Сонымен, егер біз қазіргі кездегі элементтердің жиынтығымен белгілі бір соманы алсақ, онда қосымша элементтерді пайдаланбау арқылы осы элементтерді қазіргі элементтер жиынтығымен аламыз. Бұл тривиалды. Мұны prevRowIsTrue деп атайық.
  2. Қазіргі элемент - біз дәл сол нәтижеге қол жеткізгіміз келетін сома. Бұл да маңызды емес. Мұны «isExactMatch» деп атайық.
  3. Егер жоғарыда аталған екі шарт орындалмаса, мақсатты сомаға жетудің жолы бар. Мұнда біз ағымдағы элементті - алдыңғы қатардағы элементтер жиынтығымен салыстырғанда қазіргі жолдағы элементтер жиынтығындағы қосымша элементті қолданамыз - ал қалған мақсатты сомаға жететінімізді тексереміз. Мұны canArriveAtSum деп атайық.

3-шартты шығарайық. Біз ағымдағы элементті мақсатты жиынтықтан төмен болған жағдайда ғана қолдана аламыз. Егер олар бірдей болса, 2-шарт орындалады. Егер ол үлкенірек болса, біз оны қолдана алмаймыз. Бірінші қадам - ​​бұл ағымдағы элементтің бар екеніне көз жеткізу

Ағымдағы элементті қолданғаннан кейін, қалған сома қалады. Содан кейін біз бұған қол жеткізуге болатындығын жоғарыдағы жолдағы тиісті жазбаны тексеру арқылы тексереміз.

Қалыпты КП сияқты, біз үстелді қадамнан төменге қарай құрғымыз келеді. Біз негізгі істерден бастап, түпкілікті шешімге келгенше бастаймыз.

5-қадам: жауап қайтарыңыз

Біз жай санды қайтарамыз [nums.length] [totalSum / 2].

Жұмыс коды

Оқығаныңызға рахмет!