背包算法

背包算法（knapsack algorithm），理学-计算机科学技术-计算机科学理论-算法-组合算法，背包算法是求解背包问题的算法。背包问题背包问题（knasack problem）是运筹学中一类经典的组合优化问题。在20世纪50年代首次提出背包问题， 此问题可以简述为如何利用有限的空间内装入大小和收益各不相同的物品，以此实现所装物品的价值最大化。背包问题的研究无论从理论还是实践上都有重要的意义。在理论方面，背包问题已经被证明是一个NP完全问题（见NP完全性）。在现实应用方面，背包问题具有很多的现实背景，如公钥密码，预算成本控制，资源分配，投资决策，货仓的装载，存储器空间的分配等。根据背包应用的不同，研究者们提出一些变形的背包问题，其中包括：0-1背包问题（0-1 knapsack problem）、多目标背包问题（multiobjective knapsack problem）、二次背包问题（quadratic knapsack problem）等。