01背包变题 | #装箱问题#

#include <bits/stdc++.h>
using namespace std;
 


/**

有一个箱子容量为 V ，同时有n个物品，每个物品有一个体积（正整数）。每个物品只能使用一次。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

*/

 
int main()
{

    int V,n;
    cin>>V>>n;
    vector<int> a(n); 
    int no = 0;
    vector<int> dp(V+1,no); 
    for(int i=0;i<n;i++) 
        cin>>a[i];
    for(int i=0;i<n;i++) {
        for(int j=V;j>=a[i];j--)
            dp[j] = max(dp[j],dp[j-a[i]]+a[i]);
    }
    cout << V- dp[V] <<endl;
    
    return 0;
}