01背包问题如何求得最佳取法，而不仅是最大价值。

cobras

01背包问题如何求得最佳取法，而不仅是最大价值。
兄弟不才，只知道最大值，而不知如何取。

fender0107401

整数规划基本上就是个恶梦。

这个问题，我虽然没有仔细研究过，但是我感觉对于大规模问题来说，没有什么好算法去找全局最优解，有个满意解也就了。

而且实际当中的很多问题就是直接求满意解的，至少比没有解好。

小规模的，怎么都好说，关键是大规模的。

很多专业的计算软件都对整数规划没办法，因为缺乏对应的理论工具。

就是是一般的无约束的非线的非凸规划，也没啥办法。

什么多下降类算法，多初始点的下降类算法、群类算法、都没有办法保证理论上的全局最优。。。

fender0107401

有个算法叫分支定界法，比较有意思，你可以去玩玩。。。

koolcoy

最佳如何定义？

folklore

回复 2# fender0107401


    我以后有空给你发个double规划的， 用callback的返回值来界定最佳值。
根据callback（如为null, 有default的callback）不同, 可以找到小于目标的最佳值， 大于目标的最佳值， 和目标值最接近的最佳值（绝对值）；
如果找到的最佳值相等， 选择数目最小的那个组合；

当然， 这种算法要找的值为“最佳”， 那只能是遍历。

fender0107401

回复 5# folklore

哈哈。

cokeboL

各位大神都太注重算法了

游戏这种项目，背包容量是分阶段扩展的，物品种类也就那些种，一般情况，数量级不是很大

对于可能存在的各种物品最大数量，事先算出各种容量小于背包容量的组合，按value从大到小存在数组并配在文件里，[1] = "A5B3C4", [2] = "A5B3C3"

根据目前的背包容量，在配置文件里读出所有可能的组合数组，遍历看当前物品能否满足，比如"A5B3C4"，看当前已有物品是否足够5个A3个B4个C，够的话就用"A5B3C4"，否则找下一个稍小的value数组

cobras

没关系，都可以转换为01背包。只有东西不是无限多就行了。

cobras

我看了一篇博客上有01背包的详细解法。要知道具体选法要N*V的空间？