生命不息,奋斗不止

题解 UVA1149 【装箱 Bin Packing】

2020-07-22 07:42:03


看到这篇题目,就可以明显感知到,这是一道背包问题。并且还是背包问题的最经典的例子。背包问题 $ DP $ 和 $ DFS $ 都可以解决。这道题数据量不算大,用DFS做应该也没问题,但大部分背包问题数据都很大。1000的数据量,$ O(n^2) $ 也够呛!保险起见,本人使用$ DP $来写。 动态规划的方法很简单,定义一个f数组,第一维存当前的编号,第二维存到现在为止一共要用的时间。f[i][j]就是前i个草药用j个单位时间最大价值。这样一来就很好理解了吧。用双重循环扫,依次枚举编号和时间。

下面的代码供大家参考

#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;
}