题解 | [NOIP2001]装箱问题

#include <iostream>
using namespace std;
int a[100010],dp[100010];
int main() {
    int v,n;cin>>v>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    for(int i = 1;i<=n;i++){
        for(int j = v;j>=0;j--){
            if(j>=a[i]){
                dp[j] = max(dp[j],dp[j-a[i]]+a[i]);
            }
            
        }
    }
    cout<<v-dp[v];
    return 0;
}
// 64 位输出请用 printf("%lld")

状态转移方程为当剩余空间可以装当前物品时，dp[i] = max(dp[i],dp[i-a[i]]+a[i])选第i个和不选第i个。

活动地址https://www.nowcoder.com/discuss/726480854079250432