Ang fractional knapsack na problema sa C++ ay tumutukoy sa pagtukoy ng isang paraan upang punan ang isang bag ng mga item na may partikular na timbang at tubo sa paraang naglalaman ang bag ng pinakamataas na halaga nang hindi lalampas sa maximum na limitasyon.
Paano Lutasin ang Fractional Knapsack Problem sa C++
Dahil sa isang hanay ng mga item, bawat isa ay may ibinigay na timbang at tubo, tukuyin ang bawat bilang ng mga item sa naturang kumbinasyon na ang kabuuang bigat ng mga item ay mas mababa sa maximum na limitasyon ng bag, ngunit ang halaga ay dapat na panatilihing malaki hangga't maaari.
Algorithm Upang Ipatupad ang Fractional Knapsack Problem
Ang paggana ng algorithm ng Knapsack ay mauunawaan sa pamamagitan ng mga sumusunod na punto:
- Kumuha ng dalawang hanay ng timbang at kita.
- Itakda ang maximum na halaga ng sako sa W.
- Tukuyin ang density sa pamamagitan ng pagkuha ng ratio ng parehong mga parameter.
- Pagbukud-bukurin ang mga item sa pagpapababa ng pagkakasunud-sunod ng density.
- Magdagdag ng mga halaga hanggang ito ay <=W.
Ang Sakim na Diskarte upang Malutas ang Fractional Knapsack Problem
Ang sakim na diskarte ay naglalayong gumawa ng mga perpektong pagpipilian sa bawat hakbang, na humahantong sa perpektong solusyon sa dulo. Nilulutas nito ang mga problema nang hakbang-hakbang na humahantong sa mga konklusyon sa halip na tapusin ang mga resulta sa dulo lamang. Ito ay isang source code para sa pagpapatupad ng isang solusyon sa fractional knapsack na problema sa C++:
#include
gamit namespace std ;
struct Bagay {
int halaga, timbang ;
Bagay ( int halaga, int timbang )
: halaga ( halaga ) , timbang ( timbang )
{
}
} ;
bool cmp ( struct Bagay x, struct Bagay y )
{
doble A1 = ( doble ) x. halaga / x. timbang ;
doble A2 = ( doble ) at. halaga / at. timbang ;
bumalik A1 > A2 ;
}
doble fractionalKnapsack ( struct Object arr [ ] ,
int SA, int laki )
{
uri ( arr, arr + laki, cmp ) ;
int curWeight = 0 ;
doble pangwakas na halaga = 0.0 ;
para sa ( int i = 0 ; i < laki ; i ++ ) {
kung ( curWeight + arr [ i ] . timbang <= SA ) {
curWeight + = arr [ i ] . timbang ;
pangwakas na halaga + = arr [ i ] . halaga ;
}
iba pa {
int manatili = SA - curWeight ;
pangwakas na halaga + = arr [ i ] . halaga
* ( ( doble ) manatili
/ arr [ i ] . timbang ) ;
pahinga ;
}
}
bumalik pangwakas na halaga ;
}
int sa = 60 ;
Object arr [ ] = { { 100 , dalawampu } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int laki = sukat ng ( arr ) / sukat ng ( arr [ 0 ] ) ;
cout << 'Maximum na kita = '
<< fractionalKnapsack ( arr, v, laki ) ;
bumalik 0 ;
}
Sa code na ito, tinukoy ang isang istraktura ng bagay na may mga halaga ng timbang at kita na nakaimbak dito. Ang bool cmp() ay ginagamit upang gumawa ng paghahambing sa pagitan ng dalawang bagay batay sa ratio ng timbang at halaga ng dalawang bagay. Ang array ay nakaayos sa pababang pagkakasunud-sunod at ang halaga ay patuloy na nagdaragdag hanggang umabot ito sa maximum. Kung ang kasalukuyang halaga ay pinahihintulutan at sa loob ng limitasyon, ito ay idinagdag, kung hindi man ang pinababang ratio nito ay idinagdag sa bag. Ang magnitude ng timbang at halaga ay input sa pangunahing code at ang pinakamataas na kita ay naka-print sa output.
Ang pinakamataas na kita na naimbak sa meryenda ay 580.
Konklusyon
Ang fractional knapsack na problema sa C++ ay tumutukoy sa pagtukoy ng isang paraan upang punan ang isang bag ng mga item na may partikular na timbang at tubo sa paraang naglalaman ang bag ng pinakamataas na halaga nang hindi lalampas sa maximum na limitasyon. Ito ay maaaring makamit sa pamamagitan ng sakim na diskarte na naglalayong gumawa ng mga perpektong pagpipilian sa bawat hakbang, na humahantong sa perpektong solusyon sa dulo.