论文标题
{0,1} -knapsack问题具有定性级别
The {0,1}-knapsack problem with qualitative levels
论文作者
论文摘要
考虑了经典背包问题的一种变体，其中每个项目都与整数重量和定性水平相关联。我们定义了给定项目集的可行子集的优势关系，并表明此关系定义了预订。我们提出了一种动态编程算法来计算整个非主导的秩基数向量，并陈述了两种贪婪的算法，该算法有效地计算了一个有效的解决方案。
A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We define a dominance relation over the feasible subsets of the given item set and show that this relation defines a preorder. We propose a dynamic programming algorithm to compute the entire set of non-dominated rank cardinality vectors and we state two greedy algorithms, which efficiently compute a single efficient solution.
