算法入门-[NOIP2001]装箱问题

[NOIP2001]装箱问题

https://ac.nowcoder.com/acm/problem/16693

题意

  • n个物品,箱子体积为v,装入物品后,箱子的最小剩余体积是多少

思路

  • 动态规划

  • 对于每一个物品,考虑放或者不不放,观察体积

  • 即维护放入前i个物品能否满足体积为j

  • (当前物品已经比需要的体积大了,放不进去)

  • (当前物品可以放的进去,考虑放/不放)

  • 特别的,本题有三种写法:正常dp,01滚动,就地滚动

  • 因为每一行的值之和上一行有关,且我们只在乎最后一行的值,每次更新的时候只用看前一行,所以只用两行来存,一行是当前行,一行是上一行,把原来的行号变成mod2意义下的行号即可(01滚动)

  • 由于上一行有的值下一行一定也满足,所以我们可以直接在原有行的基础上改动(就地滚动)

  • 注意:如果就地滚动的话要从没维护的开始,到体积无法容纳当前物体为止,避免一个物品被重复维护

    Eg.当前物品体积为三,如果从头开始滚动,到j=3时,dp[3]=dp[0],到j=6时,dp[6]=dp[3]……造成错误

AC代码

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

int dp[505050];

int main(){
    int v,n;
    cin >> v >> n ;
    int a[50] = {0};
    for(int i=1;i<=n;i++) cin >> a[i]; 
    //v1:正常dp
    // dp[0][0]=1;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<=v;j++){
    //         if(a[i]>j) dp[i][j]=dp[i-1][j];
    //         else dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]];
    //     }
    // }
    // for(int i=v;i>=0;i--){
    //     if(dp[n][i]){
    //         cout << v-i <<endl;
    //         break;
    //     }
    // }
    //v2:01滚动,压缩到两行内
    // dp[0][0]=1;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<=v;j++){
    //         if(a[i]>j) dp[i%2][j]=dp[(i-1)%2][j];
    //         else dp[i%2][j] = dp[(i-1)%2][j] || dp[(i-1)%2][j-a[i]];
    //     }
    // }
    // for(int i=v;i>=0;i--){
    //     if(dp[n%2][i]){
    //         cout << v-i <<endl;
    //         break;
    //     }
    // }
    //v3:就地滚动,只占用一行
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i];j--){
            if(dp[j-a[i]]) dp[j] = dp[j-a[i]];
        }
    }
    for(int i=v;i>=0;i--){
        if(dp[i]){
            cout << v-i <<endl;
            break;
        }
    }
    return 0;
}

全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
uu们,拒offer时hr很生气怎么办我哭死
爱睡觉的冰箱哥:人家回收你的offer,或者oc后没给你发offer的时候可不会愧疚你,所以你拒了也没必要愧疚他。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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