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

装箱问题

https://www.nowcoder.com/practice/c990bd0bf8e04bfbb19c0964401c8f77

不知道为什么要套背包的做法,其实一维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")

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
07-01 13:37
门头沟学院 Java
steelhead:不是你的问题,这是社会的问题。
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务