[NOIP 2001 普及组] 装箱问题

知识点

动态规划、01背包

解题思路

dp[c]表示容量不超过c时能装入的最大总体积。遍历每件体积v，按c从V到v倒序更新dp[c]=max(dp[c],dp[c-v]+v)。答案为V-dp[V]。

正确性说明

处理一件物品时，方案分为不装与装两种。前者沿用旧dp，后者由未使用当前物品的容量c-v最优方案加上v得到；倒序保证后者状态仍来自上一层，因此每件最多使用一次。归纳得dp[V]最大，剩余最小。

易错点

容量循环正序会变成物品可重复使用；物品大于箱子可跳过；不能贪心只选最大的。

复杂度

时间O(nV)，空间O(V)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int V,n;cin>>V>>n;vector<int>dp(V+1);while(n--){int v;cin>>v;for(int c=V;c>=v;c--)dp[c]=max(dp[c],dp[c-v]+v);}cout<<V-dp[V]<<'\n';}