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

滚地数组

#include <iostream>
using namespace std;
int a[40];
int f[20020]; //数组滚动
int n, v;

int main(){
    cin >> v >> n;
    for(int i = 1;i <= n;++ i) cin >> a[i];
    f[0] = 1; //初始化
    
    for(int i = 1;i <= n;++ i){
        for(int j = v;j >= a[i];j --){ //j从0开始遍历到v,然后选与不选都设置为真
                f[j] = f[j] || f[j - a[i]];
        }
    }
    int ans = 0;
    for(int i = v;i >= 0;i --){ //倒序遍历
        if(f[i]){ //只要有为真的就说明此时是体积剩余最小的
            ans = v - i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}