最近小弟在研究一个运费的问题卡关很久
题目大概是有2吨车、5吨车、10吨车
载一趟的运费分别是850、1600、3000
货物有
A:17吨 B:21吨 C:18吨 D:14吨 E:7吨
不同的货可以并车，多载一种货加收300元
但最多只能载三种货
请问怎样的出车组合运费最低？
-
这是一个例子，但最终目的是要写成一个通解
车子、运费、货物、并车次数都会是变量
-
我的想法是超过10吨的货都先用10吨车载
建立两个表（两个货一定并车运费最低的组合
和三个货一定并两次车运费最低的组合）
所以这两个表的字段就会是总重2~18吨、3～27吨
http://imgur.com/T3ielJ6
这是我用手算的2～18吨表(总重3比较特别 可以不并车）
最后再从除以10之后的货物中挑出最佳解(目前只想到穷举挑法）
-
可是我目前遇到的困难卡在建表
感觉跟ＤＰ很相似（换硬币问题）
可是硬币问题是数量刚刚好
但这个问题车的载重量可能大于货物总重
所以不知道怎么列出各种组合再算运费
请问有没有人有想法建表或是整个问题有别的解法
感恩