题解 UVA1149 【装箱 Bin Packing】

· · 题解

看到这篇题目，就可以明显感知到，这是一道背包问题。并且还是背包问题的最经典的例子。背包问题 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;
}