背包问题模型及测试集简介_背包问题数据集

1、背包问题描述

背包问题(Knapsack Problem，KP)是一种重要的组合优化问题，在生活的许多领域都有着十分广泛的应用。背包问题可以描述为：给定一个背包和n种物品，其中，背包的容量为$V$ ，第i 种物品的质量为 $c_i$ ，价值为 $p_i$ ，如何通过物品选择，使得装入背包中的物品总价值最大。其数学模型如下：
f = max ⁡ ∑ i = 1 n p i x i  s.t.  ∑ i = 1 n c i x i ≤ V , i = 1 , 2 , … , n x i = 0 , 1

$$\begin{array}{ll} & f=\max \sum_{i=1}^{n} p_{i} x_{i} \\ \text { s.t. } & \sum_{i=1}^{n} c_{i} x_{i} \leq V, i=1,2, \ldots, n \\ & x_{i}=0,1 \end{array}$$  s.t. ​f=max∑i=1n​pi​xi​∑i=1n​ci​xi​≤V,i=1,2,…,nxi​=0,1​

2、背包问题测试集

选取9个经典的背包问题测试集，下表中，$c$为物品的质量，$p$为物品的价值，$V$为背包的最大容量。

参考文献：
[1]耿亚,吴访升.基于粒子群-模拟退火算法的背包问题研究[J].控制工程,2019,26(05):991-996.DOI:10.14107/j.cnki.kzgc.161767.