Проблемът с раницата е

раница англ Проблем

Проблемът с раницата (раницата) (англ. Проблем с раницата ) Е един от проблемите на комбинаторната оптимизация. Той получи името си от проблема за максимизиране на опаковането на колкото се може повече необходими неща в раница, при условие че общият обем (или теглото) на всички предмети, които могат да се поберат в раницата, е ограничен. Очевидно никой няма да напише програма за опаковане на раница по време на пътуване. Има по-широко приложение. Проблеми с товаренето (около раницата) и нейното модифициране често възникват в икономиката, приложната математика, криптографията, логистиката, за да се намери оптималното натоварване на транспорт (самолет, влак, трюм) или склад [1] [2], генетика. Като цяло проблемът може да бъде формулиран по следния начин: от даден набор от елементи със свойствата "стойност" и "тегло" е необходимо да се избере определен брой елементи по такъв начин, че да се получат максималните общи разходи, докато спазвайки ограничението върху общото тегло.

Съдържание

Класическа постановка на проблема

Нека има набор от елементи, всеки от които има два параметъра - тегло и стойност. И има раница с определен капацитет. Предизвикателството е да съберете раницата с максималната стойност на предметите вътре, като същевременно спазвате ограничението за тегло на раницата.

Математически това може да се формулира по следния начин: има товар. За всеки i-ти товар се определят теглото 0 "border =" 0 "/> и стойността 0" border = "0" />. Необходимо е да се опаковат в раница с ограничена товароносимост тези стоки, за които общата стойност на опакованите би била максимална [3] .

Варианти на проблема с раницата

Има много разновидности на проблема с раницата, разликите са в условията, наложени върху раницата, предметите или техния избор.

  1. Раница 0-1 (англ.0-1 раница проблем ) [един]
  2. Ограничена раница (англ.Проблем с ограничен раничка ) [4]
  3. Неограничена раница (Integer Backpack) (англ.Неограничен проблем с раницата (целочислена раница) ) [4]
  4. Раница с много възможности за избор (англ.Проблем с раници с множество възможности за избор ) [пет]
  5. Мултипликативна раница (англ.Проблем с множество раници ) [6]
  6. Многомерна раница (англ.Проблем с многомерни раници ) [пет]