题目：[NOIP2001]装箱问题 ，哈哈，我们今天来看一道很古老的题嘛，这是选自NOIP上的一道题，好了，我们一起来看看题意吧：
考虑到直接复制题目，或者截屏的方式不是很方便阅读，我就把直接题目链接放下面！
题目传送门： [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; }
我这里放一张雨巨的图，便于大家理解
我们可以看到每一行的结果实际上只与上一行有关，所以啊，我们可以压缩一下
压缩时有个坑：我们遍历体积的时候，需要从大到小去遍历，这样是为了防止让一个物品多次放入背包（这波操作真的很有意思😜）
下面我直接放代码
一维数组版
#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; }
