题解 UVA1149 【装箱 Bin Packing】
Chinshyo
2020-07-22 07:42:03
看到这篇题目，就可以明显感知到，这是一道**背包问题**。并且还是背包问题的最经典的例子。背包问题 $ DP $ 和 $ DFS $ 都可以解决。这道题数据量不算大，用DFS做应该也没问题，**但大部分背包问题数据都很大**。1000的数据量，$ O(n^2) $ 也够呛!保险起见，本人使用$ DP $来写。
动态规划的方法很简单，定义一个f数组,第一维存当前的编号，第二维存到现在为止一共要用的时间。f[i][j]就是前i个草药用j个单位时间最大价值。这样一来就很好理解了吧。用双重循环扫，依次枚举编号和时间。
### 下面的代码供大家参考
```cpp
#include<bits/stdc++.h>
using namespace std;
int t[105],v[105];
int f[105][1005];
int main()
{
int T,M;
cin>>T>>M;
for(int i=1;i<=M;i++)
{
cin>>t[i]>>v[i];
} //输入数据
for(int i=1;i<=M;i++)//依次枚举编号
{
for(int j=1;j<=T;j++)//依次枚举使用时间
{
if(t[i]>j)//超过当前可用时间，不可以取
{
f[i][j]=f[i-1][j];//不取当前，取前一个的最优解
}
else//可取
{
f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+v[i]);//取和不取中选最优（防止负数的特例）
}
}
}
cout<<f[M][T];//输出最终的最优解
return 0;
}
```