| [Mgeni (112.0.*.*)]majibu [Kichina ] | Wakati :2022-06-24 |  Ufungaji wa kuunganisha ni njia ya kawaida ya kutatua suluhisho bora kwa programu ya mstari wa integer.
Fasili:
Kutafuta vizuri mfumo wa nafasi zote za suluhisho zinazowezekana kwa shida ya uboreshaji iliyozuiliwa ambayo suluhisho linalowezekana ni nambari ya mwisho ni nini tawi na delineating ni juu. Ni kawaida kugawanya mara kwa mara nafasi nzima ya suluhisho katika sehemu ndogo na ndogo, inayoitwa matawi; Na seti ya suluhisho ndani ya kila sehemu ndogo huhesabiwa kama lengo la chini lililofungwa (kwa shida ya chini), ambayo inaitwa delimitation. Baada ya kila tawi, ikiwa thamani ya lengo la seti ya suluhisho inayojulikana haifikii mpaka wa sasa, sehemu ndogo imezungushwa. Kwa njia hii, subsets nyingi hazizingatiwi, ambayo inaitwa kupogoa. Hii ni wazo la njia ya matawi.
Mandharinyuma:
Njia iliyofungwa ya matawi inaweza kutumika kutatua matatizo safi ya programu ya integer au mchanganyiko. Ilipendekezwa katika miaka ya 1960 na Land Doig na Dakin, kati ya wengine. Rahisi na rahisi kutatua na kompyuta, njia hii imetumika kwa mafanikio kutatua matatizo ya ratiba ya uzalishaji, matatizo ya mauzo ya kusafiri, matatizo ya eneo la kiwanda, matatizo ya backpack na matatizo ya usambazaji.
Mawazo:
Kuna shida ya programu ya integer iliyoongezwa A, na shida yake ya programu ya mstari inayolingana B. Kuanzia suluhisho la shida B, ikiwa suluhisho lake bora halikidhi hali ya integer ya A, basi kazi bora ya lengo la B lazima iwe imefungwa juu ya kazi bora ya lengo la A z *, iliyofafanuliwa z ̄; Thamani ya kazi ya lengo la suluhisho lolote linalowezekana kwa z itakuwa z_ ya chini iliyofungwa z_ z. Njia ya matawi ni njia ya kugawanya uwanja unaowezekana wa B katika mikoa midogo. Hatua kwa hatua kupunguza z na kuongeza z_. Hatimaye pata z*. |
|
