BriefGPT.xyz
Jul, 2023
背包问题:连通性、路径和最短路径
Knapsack: Connectedness, Path, and Shortest-Path
HTML
PDF
Palash Dey, Sudeshna Kolay, Sipra Singh
TL;DR
我们研究了具有图论约束的背包问题,证明了该问题是NP完全问题,并提出了一个在多项式时间内运行的算法以及一个近似算法。
Abstract
We study the
knapsack problem
with
graph theoretic constraints
. That is, we assume that there exists a graph structure on the set of items of knapsack and the solution also needs to satisfy certain graph theoreti
→