人群分配算法问题

Question

想用php实现如下场景
有10张票
每张票报名名额不定，每个名额代表一个人
已知总报名人数30人(多张票且每张票人数不定)
现有两辆车，一辆可坐17人一辆可坐13人
如何通过票来分配人群到某辆车？
假设票无法拆分，同一张票的一群人只能坐一辆车
如何安排使得最后无法安排的票券人数最少？(无法安排的票：假设第一辆车还剩1个位置第二辆还剩3个位置，只剩一张4个位置的票没有安排)

Answer 1

就相当于经常玩的游戏，有三根柱子，有十个高度不等的环，要套在三根柱子上，最后使三根柱子的圆环高度相等。十月份我们做了一个项目是采用插空的方式。按照票面序号去安排车辆及座位。遇到坐不下的就自动安排到下一辆车。这种方式的缺点是座位利用率不高。最好的方式是根据每一辆车的座位，从车票中选取能坐的人。组合完成后自动发放座位号

Answer 2

不好意思,刚看到邀请,sf的消息通知做的.. ..工作完毕后,回来修改.

Answer 3

这是一个背包问题。
和普通的背包不一样的地方，普通的背包问题用1维数组dp[w]就能解决。
这里有两个背包，所以要用一个2维数组dpw1来记录当前售票人数最多的状态(w1,w2分别为两辆车的座位数）