The 2022 ICPC Asia Hangzhou Regional Programming Contest C. No B
2022-12-07 20:37 作者:Asunataisiki | 我要投稿
题意：个物品，背包容量为
，对于第
个物品有其体积
,对于任意
，都有其对应的价值
，若当前背包可以装下整个物品，那么就可以获得
的价值，否则获得
，求最大价值
思路：很显然的01背包问题，但是要注意到，如果能装下整个物品那么必须装入整个物品，否则才能装入部分物品，因此只可能会有一个物品被选择了一部分体积的价值，而剩下的被选择的物品一定是被选择了全部体积的价值，因此可以定义表示前
个物品，体积为
，前
个物品中是否有选择部分体积的物品（0表示没有选过，1表示选过）
