Проблемът с частичната раница в C++ се отнася до идентифициране на начин за напълване на чанта с предмети с дадено тегло и печалба по такъв начин, че чантата да съдържа максималната стойност, без да надвишава максималната граница.
Как да решите проблема с дробната раница в C++
Даден е набор от артикули, всеки с дадено тегло и печалба, определете всеки брой артикули в такава комбинация, че общото тегло на артикулите да е по-малко от максималното ограничение на торбата, но стойността трябва да бъде възможно най-голяма.
Алгоритъм за прилагане на проблема с дробната раница
Функционирането на алгоритъма Knapsack може да се разбере чрез следните точки:
- Вземете два масива от тегло и печалба.
- Задайте максималната стойност на чувала на W.
- Определете плътността, като вземете съотношението на двата параметъра.
- Сортирайте елементите в низходящ ред на плътност.
- Добавете стойности, докато стане <=W.
Алчният подход за решаване на проблема с частичната раница
Алчният подход има за цел да прави идеални избори на всяка стъпка, водещи до идеалното решение в края. Той решава проблемите стъпка по стъпка, водещи до заключения, вместо да заключава резултатите само в крайна сметка. Това е изходен код за прилагане на решение на проблема с частичната раница в C++:
#include
използвайки пространство от имена std ;
структура Обект {
вътр стойност, тегло ;
Обект ( вътр стойност, вътр тегло )
: стойност ( стойност ) , тегло ( тегло )
{
}
} ;
bool cmp ( структура Обект x, структура Обект y )
{
двойно A1 = ( двойно ) х. стойност / х. тегло ;
двойно A2 = ( двойно ) и. стойност / и. тегло ;
връщане A1 > A2 ;
}
двойно fractionalKnapsack ( структура Обект обр [ ] ,
вътр IN, вътр размер )
{
вид ( обр, обр + размер, cmp ) ;
вътр CurWeight = 0 ;
двойно крайна стойност = 0,0 ;
за ( вътр аз = 0 ; аз < размер ; аз ++ ) {
ако ( CurWeight + обр [ аз ] . тегло <= IN ) {
CurWeight + = обр [ аз ] . тегло ;
крайна стойност + = обр [ аз ] . стойност ;
}
друго {
вътр остават = IN - CurWeight ;
крайна стойност + = обр [ аз ] . стойност
* ( ( двойно ) остават
/ обр [ аз ] . тегло ) ;
прекъсвам ;
}
}
връщане крайна стойност ;
}
вътр в = 60 ;
Обект обр [ ] = { { 100 , двадесет } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
вътр размер = размер на ( обр ) / размер на ( обр [ 0 ] ) ;
cout << 'Максимална печалба = '
<< fractionalKnapsack ( arr, v, размер ) ;
връщане 0 ;
}
В този код е дефинирана обектна структура, която има съхранени стойности на тегло и печалба. Bool cmp() се използва за извършване на сравнение между два обекта въз основа на съотношението на теглото и стойността на два обекта. Масивът е подреден в низходящ ред и стойността продължава да се добавя, докато достигне максимума. Ако текущата стойност е допустима и в границите, тя се добавя, в противен случай нейното намалено съотношение се добавя към торбата. Големината на теглото и стойността се въвежда в основния код и максималната печалба се отпечатва на изхода.
Максималната печалба, съхранена в снака, е 580.
Заключение
Проблемът с частичната раница в C++ се отнася до идентифициране на начин за напълване на чанта с предмети с дадено тегло и печалба по такъв начин, че чантата да съдържа максималната стойност, без да надвишава максималната граница. Това може да се постигне чрез алчния подход, който има за цел да прави идеални избори на всяка стъпка, водещи до идеалното решение в края.