【贪心+01背包】The Highest Mark

传送门:【HDU5501】The Highest Mark

分析:贪心+01背包

贪心求解做题顺序,动态规划求解做哪个题。

注意贪心规则的选取。对于两个题目的选择上,列出先做A再做B的得分,和反过来的得分,求解当第一个的分比第二个大的情况。解此不等式,得到贪心规则。之后用普通的0-1背包解决。注意数组不要开小了。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
typedef long long LL;
using namespace std;

LL dp[3050];

struct Problems
{
  int a, b;
  int cost;
}problems[1050];

bool cmp(Problems &o1, Problems &o2)//贪心化
{
  if (o1.b*o2.cost > o2.b*o1.cost) return true;
  else return false;
}
int main()
{
  int t = 0;
  cin >> t;
  while (t--)
  {
    memset(dp, 0, sizeof(dp));
    int n, time;
    cin >> n >> time;
    for (int i = 1; i <= n; i++)
    {
      cin >> problems[i].a >> problems[i].b >> problems[i].cost;
    }
    sort(problems + 1, problems + n + 1 ,cmp);
    int sum_time=time,get_value=0,used=0;
    //动态规划
    int ans = INT_MIN;
    for (int i = 1; i <= n; i++)
      for (int j = time; j >= problems[i].cost; j--)
        dp[j] = max(dp[j], dp[j - problems[i].cost] + (problems[i].a - problems[i].b*j));
    for (int i = 1; i <= time; i++)
    {
      if (dp[i] > ans)
        ans = dp[i];
    }
    cout << ans << endl;
  }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 × 1 =