散文網(wǎng) » 生活 »日常 » The 2022 ICPC Asia Hangzhou Regional Programming Contest C. No B

The 2022 ICPC Asia Hangzhou Regional Programming Contest C. No B

2022-12-07 20:37 作者:Asunataisiki 0人讀過 | 我要投稿

題意： $n$ 個物品，背包容量為 $k$ ，對于第 $i$ 個物品有其體積 $p_i$ ,對于任意 $t%5Cin%20%5B1%2Cp_i%5D$ ，都有其對應(yīng)的價值 $w_%7Bi%2Ct%7D$ ，若當前背包可以裝下整個物品，那么就可以獲得 $w_%7Bi%2Cp%5Bi%5D%7D$ 的價值，否則獲得 $w_%7Bi%2Ck-sum%7D(sum%E4%B8%BA%E5%BD%93%E5%89%8D%E8%A3%85%E5%85%A5%E7%89%A9%E5%93%81%E7%9A%84%E6%80%BB%E4%BD%93%E7%A7%AF)$ ，求最大價值

思路：很顯然的01背包問題，但是要注意到，如果能裝下整個物品那么必須裝入整個物品，否則才能裝入部分物品，因此只可能會有一個物品被選擇了一部分體積的價值，而剩下的被選擇的物品一定是被選擇了全部體積的價值，因此可以定義 $dp_%7Bi%2Cj%2Ck%7D$ 表示前 $i$ 個物品，體積為 $j$ ，前 $i$ 個物品中是否有選擇部分體積的物品（0表示沒有選過，1表示選過）