题解 | #装箱问题# 非背包的做法

不知道为什么要套背包的做法，其实一维dp数组就够了，时间复杂度O(nV)，空间复杂度O(V)

#include <iostream>
#include <vector>
using namespace std;
void printa(vector<bool>& a){
    for(auto c:a){
        cout<<c<<' ';
    }
    cout<<endl;
}
int main() {
   int V,n,t,i,j,maxV=0,boundary;
   cin>>V>>n;
   //cout<<V<<' '<<n<<endl;
   vector<bool> dp(V+1);
   dp[0]=true;
    for(i=0;i<n;++i){
        cin>>t;
        if(dp[V-t]){
            maxV=V;
            break;
        }
        boundary=min(maxV,V-t);

        for(j=boundary;j>=0;--j){
            //注意这里要反向遍历，因为正向遍历会踩到被修改的格子
            if(dp[j]){
                dp[j+t]=true;
                maxV=max(maxV,j+t);
            }
            
        } 
       // cout<<t<<' '<<maxV<<' '<<boundary<<endl;
       //printa(dp);
       

    }

    cout<<V-maxV<<endl;
}
// 64 位输出请用 printf("%lld")