这道题算是做的第一道需要排序的dp题,太弱了,看了解题报道都半天不懂为什么要按照p-q的顺序排序。。。。
解题思路:与顺序有关的01背包。初看之下似乎和普通背包差不多,判容量大于q时才装。但是这会出大问题,如果一个物品p = 5,q = 7,一个物品p = 5,q = 9,如果先算第一个,那么当次只有7,8...m可以进行状态转移,装第二个物品的时候9,10..m进行转移,第二个物品转移就可以借用第一个物品的那些个状态,而第二个物品先转移,第一个再转移则不能。当然,还有价格有关,当限制一样价格不同时顺序就影响结果。
q-p小的先选。
因为......
阅读全文