NOIP 装箱问题

ゝ一纸荒年。 2024-04-20 07:21 77阅读 0赞

⭐**简单说两句**⭐

> **作者：****后端小知识**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

题目：\[NOIP2001\]装箱问题  ，哈哈，我们今天来看一道很古老的题嘛，这是选自NOIP上的一道题，好了，我们一起来看看题意吧：

考虑到直接复制题目，或者截屏的方式不是很方便阅读，我就把直接题目链接放下面！  
题目传送门： [\[NOIP2001\]装箱问题][NOIP2001]

`思路`:

> 写过01背包的老板看到这道题时，嘴角微微上扬，说，这还不简单,分分钟AC?
> 
> `但是`,我这里用另一种动态规划的思路
> 
> 先说说为什么要用动态规划吧：如果用暴力法的话（枚举每个物品装箱还是不装箱），时间复杂度会很高 O(2^n) ?, 我们需要降低时间复杂度。
> 
> 举个例子：背包容量 20， 5个物品，体积分别为，1,2,2,4,5 ，若我们枚举每个物品放不放的话，时间复杂度是 2^5 ，我们思考下，可以发现我们放两个体积为2的物品和放一个体积为4的物品，对结果是没有影响的。 **我们算出这些物品可以放出的体积有： 1,2,3,4,5,6,7,8,9,10,11,12,13,14 这里一共14次（不排除算错的可能哈?），而暴力法的话，有32种情况。**
> 
> 我们采用动态规划的思想呢，时间复杂度为：**物品个数\*背包体积**

`我们来看看成功AC的代码吧：`

二维数组版

#include<bits/stdc++.h>
    using namespace std;
    int n,total;
    int v[20010];
    int f[35][20010];
    int main(){
        
        f[0][0]=1;
        cin>>total>>n;
        for(int i=1;i<=n;i++) cin>>v[i];
        /**
         * f[i][j] 表示 0到i 的物品能否填满容量为 j 的背包
         */
         for(int i=1;i<=n;i++){
        
             for(int j=0;j<=total;j++){
        
                 // f[i-1][j] 就表示前面 i-1 件物品能否填满容量为j的背包
                 // f[i-1][j-v[i]] 表示前面 i-1 件物品能否填满容量为j-v[i]的背包
                 if(j>=v[i]) f[i][j]=f[i-1][j]||f[i-1][j-v[i]];
                 else f[i][j]=f[i-1][j];
             }
         }
         int ans=0;
         for(int i=total;i>=0;i--){
        
             if(f[n][i]==1){
        
                 ans = i;break;
             }
         }
         cout<<total-ans;
        return 0;
    }

我这里放一张雨巨的图，便于大家理解

![image-20221128192238173][]

**我们可以看到每一行的结果实际上只与上一行有关，所以啊，我们可以压缩一下**

压缩时有个坑：我们遍历体积的时候，需要从大到小去遍历，这样是为了防止让一个物品多次放入背包（这波操作真的很有意思?）

**下面我直接放代码**

一维数组版

#include<bits/stdc++.h>
    using namespace std;
    int n,total;
    int v[20010];
    int f[20010];
    int main(){
        
        f[0]=1;
        cin>>total>>n;
        for(int i=1;i<=n;i++) cin>>v[i];
        for(int i=1;i<=n;i++){
        
             for(int j=total;j>=v[i];j--){
        
                 f[j]=f[j]||f[j-v[i]];
             }
         }
         int ans=0;
         for(int i=total;i>=0;i--){
        
             if(f[i]==1){
        
                 ans = i;break;
             }
         }
         cout<<total-ans;
        return 0;
    }

【都看到这了，点点赞点点关注呗，爱你们】??

![抽象工厂  引导关注][b18eca4c9989f60dd1e178dc2c80ec47.png]

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!???

**作者：****后端小知识**

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[NOIP2001]: https://ac.nowcoder.com/acm/problem/16693
[image-20221128192238173]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a37a7a46a6a241a9915026b70063d2fe.png
[b18eca4c9989f60dd1e178dc2c80ec47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7d01a399654e4579891629747147f49c.png