The 2022 ICPC Asia Hangzhou Regional Programming Contest C. No B
2022-12-07 20:37 作者:Asunataisiki | 我要投稿
題意：個物品，背包容量為
，對于第
個物品有其體積
,對于任意
，都有其對應(yīng)的價值
，若當前背包可以裝下整個物品，那么就可以獲得
的價值，否則獲得
，求最大價值
思路：很顯然的01背包問題，但是要注意到，如果能裝下整個物品那么必須裝入整個物品，否則才能裝入部分物品，因此只可能會有一個物品被選擇了一部分體積的價值，而剩下的被選擇的物品一定是被選擇了全部體積的價值，因此可以定義表示前
個物品，體積為
，前
個物品中是否有選擇部分體積的物品（0表示沒有選過，1表示選過）
標簽：
