我试图调和两个看似矛盾的想法：
- 已知无界背包优化问题是 NP-hard
- 我的同事和我认为我们可以使用 A* 在多项式时间内解决它的微小变化
听起来很疯狂，对吧？那就是我所想的！
问题的变化是用货机来描述的，货机必须卸下一些货物才能将其有效载荷减少到飞机的容量。所以有一组物品，每个物品都有一个重量和一个价值，以及一个必须卸载的目标重量——优化要卸载的货物，以便您至少去除 W 重量，并最小化货物的总价值。考虑一个无界问题，其中 N 种不同类型中的每一种都有任意多的可用项目。
建议的解决方案使用一个从节点（顶点）开始的图，该节点表示没有卸载。每个卸载操作都代表一条边，因此图表从起始点呈指数增长，每个可能的货物组合都已卸载。目标节点是一个虚拟聚合，总权重>=目标的所有组合都被视为目标节点。到目前为止卸载的总重量存储在每个节点中，用于确定是否已达到目标。每条边的成本是被卸载物品的价值。因此，Dijkstra 或 A* 等最短路径算法将找到最优的商品集。
Dijkstra 显然需要指数级的时间，因为它正在探索所有可能的组合。但是通过可接受的启发式，我认为 A* 应该在多项式时间内运行。我认为以下启发式应该有效。对于每件商品，计算“特定价值”，即价值与重量的比率。选择具有最高比值的商品。作为给定节点的启发式方法，计算仍需要卸载的权重乘以最大特定值。这提供了一个估计，在目标重量可以通过整数数量的最优商品达到的情况下是完全正确的，或者在所有其他情况下低估了剩余的距离（重量），因为实际的商品数量需要四舍五入向上。所以启发式是可以接受的。
我还没有以任何严格的方式证明运行时复杂性。但是 A* 的工作方式，它会贪婪地向目标添加项目，快速探索最佳选项，直观地感觉它应该在 N 的多项式时间内运行。并且通过适当可接受的启发式方法，可以保证解决方案是最优的。
那么这个解决方案有什么问题呢？我绝对不相信我们已经通过应用众所周知的算法找到了一个经过充分研究的问题的新解决方案。但这似乎应该有效。