P1049 装箱问题（01背包）

P1049 装箱问题

• 要使得箱子的剩余空间最小，所占空间需要最大值
• 问题转换为：任取若干个装入箱内，占用最大空间
• 每个物品价值和体积都为v

#include<iostream>
#include<algorithm>

using namespace std; 

const int N = 2e4 + 10;

int n,m;
int f[N];

int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ ){
        int v,w; cin >> v;
        for(int j = m; j >= v; j -- ){
            f[j] = max(f[j],f[j - v] + v);
        }
    }
    cout<<m - f[m];    
    return 0;
}