相信大家都精通,orz。
本掬蒻一开始还自信认为自己挺会的,但有一问题,自己手推无果,查资料发现根本没人讲~~(脑子不太清醒)~~
为什么01背包初始化的时候如果想这样两种初始化会有不同的结果呢?
dp[0]=0, dp[2]=dp[3]=...=dp[n]=-INF
这样的初始化的 dp[i] 就表示恰好选 i 的重量的最大价值,如果说不是恰好到了重量 i 就不算,然鹅:
dp[0]=dp[1]=...=dp[n]=0
这种初始化的 dp[i] 就表示可以不恰好,但是限重为 i 的最大价值。
这是为啥啊?
orz求教