Knapsack problems with position-dependent item weights or profits
研究了三种新的背包问题，其中物品的重量或利润取决于其在背包中的位置，提出了精确的动态规划算法和完全多项式时间近似方案。
Abstract We consider three new knapsack problems with variable weights or profits of items, where the weight or profit of an item depends on the position of the item in the sequence of items packed in the knapsack. We show how to solve the problems exactly using dynamic programming algorithms with pseudo-polynomial running times and propose fully polynomial-time approximation schemes for their approximate solution.