POJ 3624 Charm Bracelet 顺便讲一下01背包

裸的01背包问题,是DP的基础题型了,没有太多好说的。

简要说一下01背包问题的状态转移特点:按两个基准纪录数据,第一个基准是我们从0~a号物品中选,第二个基准是选择的物品已经有了多少重量b,这样组成了dp数组dp[a][b],这个数组存储的是当前状态的价值是多少。接下来我们开始dp,对于每一个当前状态(最多选择到第n个物品,已经占用了w重量),我们是从两种先前状态中导出的:1.最多选择到n-1个物品(就是当前物品还没有考虑呢),占用重量w-x(x是第n个物品重量),在这个状态上,我们添加上第n个物品。2.最多选择到n-1个物品,占用重量w,在这个状态上,我们什么也不做,直接把他当成当前状态。

在这两种先前状态中选择最好的那个(有时候因为某些原因,只能选择一个,那就选唯一的那个就好),保存下来决定为当前状态,再供以后使用。

这样我们只要读取dp[i][j]的值,就是“选择1~i中的物品,重量限定为j,最高价值是?”这个问题的答案。(没有用滚动数组的话)

Leave a Reply

Scroll to top