背包算法

aimisiyou

可将背包算法转为图解法，可以得出一些结论。将（物品重量w，物品价值c）按重量w从小到大排序。找出左边K个点使其K个点的X向坐标之和小于或等于w_tol(如图中框线内的点)，再往右添加一个点就超过w_tol。可知最优解的点数不超过K。同样将（物品重量w，物品价值c）按价值c从大到小排序，找出最上边N个点使其N个点的X向坐标之和小于或等于w_tol，再往下添加一个点就超过w_tol。可知最优解的点数不小于N。剩下的就是左下角和右上角的一些组合替换问题。

aimisiyou

现在只考虑两个方框不相交的情况（若相交，减去其中的共同点wi,ci，问题转换为w_tol-wi）,若黄色方框内Y值之和大于蓝色方框内Y值之和，就减少黄色框内的一些点，替换成蓝色框中的一些点；,若蓝色框内Y值之和大于黄色方框内Y值之和（很少见），就减少蓝色框内的一些点，替换成黄色框中的一些点。

aimisiyou

若是从黄框内减少点替换成蓝色框内的点，则将蓝色框内点按点到右直线（45度角）的距离降序排列，优先替换前面的（不一定是Y值最高点）；若是从蓝框内减少点替换成黄色框内的点，则将黄色框内点按点到左直线（45度角）的距离升序排列，优先替换前面的（不一定是Y值最高点）。若不存在替换的情况，那就是最优的结果。

aimisiyou

为确保万无一失，减少黄色框内点替换成蓝色框内点时，还要加上中间小区域（三个并排点区域），即还可能替换成此区域内的点。

aimisiyou

由背包问题联想到一个博弈游戏。甲、乙轮流选取一些物品（每个物品的重量、价值已知），游戏规则：
1、甲先手只能取一个；
2、轮到选取权的人（此时为乙）可以有两种选取方式：要么只取一个重量大于前面人选取的物品重量，要么至多选取两个都不大于前面人选取重量的物品；
3、若前面人选取了两个，此时轮到有选取权的人只能在剩下的物品中任意选取一个；若前面人选取一个物品，此时轮到有选取权的人则按规则2选取。
那么甲最多能取到多少价值的物品？

aimisiyou

根据贪心算法似乎找到了一个快速接近最优解的多项式算法。