题解 | #[NOIP2001]装箱问题#

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
//目的就是计算能够装的最大体积
//首先定义dp[j]表示箱内容量为j时体积最大值
int main() {
    int m;
    int n;
    cin>>m>>n;
    int v[n];
    vector <int> dp(m+1,0);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    for(int i=0;i<n;i++){
        for(int j=m;j>0;j--){
            if(v[i]<=j){
                dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
            }
        }
    }
    cout<<m-dp[m];
    return 0;
}
// 这段代码完全可以背诵