HDU 2191 悼念512汶川大地震遇难同胞――珍惜现在,感恩生活

这个是一个多重背包问题,其实多重背包就是01背包,举个例子(其实是扒的):

¤像如果某件物品的重量为1,价值为2,数量为1000

¤我们就可以拆分成:

¤重量为1,价值为2的物品 重量为2,价值为4的物品

¤重量为4,价值为8的物品 …

¤重量为256,价值为512的物品

¤重量为489,价值为489*2的物品

简要地说,就是先拿二进制拆,拆出来1,2,4,8,16,32。。。这样的,等到拆不动了(剩下的不够下一个2进制整幂了),就把剩下的单独拿出来当成一个新物品,这样就不会丢解了。拆分完之后不就变成01背包了嘛。

Leave a Reply

Scroll to top