混合背包问题解法&示例（洛谷p1833）

灯珑LoGin

发布于 2023-10-18 10:47:52

2880

发布于 2023-10-18 10:47:52

文章被收录于专栏：龙进的专栏

混合背包问题是把01背包、完全背包、多重背包混在一起的问题，看着比较复杂，其实就是分而治之，转换为前面这三种背包问题即可。

看题：

樱花

题目背景

《爱与愁的故事第四弹·plant》第一章。

题目描述

爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 C_i(0 \le C_i \le 200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 P_i(0 \le P_i \le 100) 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 T_i(0 \le T_i \le 100)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

输入格式

共 n+1行：

第 1 行：现在时间 T_s（几时：几分），去上学的时间 T_e（几时：几分），爱与愁大神院子里有几棵樱花树 n。这里的 T_s，T_e 格式为：hh:mm，其中 0 \leq hh \leq 23，0 \leq mm \leq 59，且 hh,mm,n 均为正整数。

第 2 行到第 n+1 行，每行三个正整数：看完第 i 棵树的耗费时间 T_i，第 i 棵树的美学值 C_i，看第 i 棵树的次数 P_i（P_i=0 表示无数次，P_i 是其他数字表示最多可看的次数 P_i）。

输出格式

只有一个整数，表示最大美学值。

样例 #1

样例输入 #1

6:50 7:00 3
2 1 0
3 3 1
4 5 4

样例输出 #1

提示

100% 数据：T_e-T_s \leq 1000（即开始时间距离结束时间不超过 1000 分钟），n \leq 10000。保证 T_e,T_s 为同一天内的时间。

样例解释：赏第一棵樱花树一次，赏第三棵樱花树 2 次。

通用解题思路

只要按照以下思路去解题即可：

for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}

具体解法

题目其实是一个多重背包+完全背包的结合。因此先把多重背包的部分，转换为0-1背包。这里可以用二进制分组进行优化（但是我代码为了省事就没写）。接着，有以下的状态转移方程：

完全背包的部分：dp[j+t[i]] = max(dp[j+t[i]], dp[j]+c[i])
0-1背包的部分： dp[j] = max(dp[j], dp[j-t[i]]+c[i])

接着直接写代码就行了。

代码

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;

typedef unsigned long long ull;

#define MAXT 1005
#define MAXN 1000005

ull dp[MAXT] = {0};
ull c[MAXN] = {0};
ull t[MAXN] = {0};
bool is_inf[MAXN] = {false};
int element = 0;

ull cal_time_delta(string st, string et)
{
   int s_h, e_h;
   int s_m, e_m;

   int pos_a = 0;
   for (int i = 0; i < st.length(); ++i)
   {
      if (st[i] == ':')
      {
         pos_a = i;
         break;
      }
   }

   int pos_b = 0;
   for (int i = 0; i < et.length(); ++i)
   {
      if (et[i] == ':')
      {
         pos_b = i;
         break;
      }
   }

   s_h = stoi(st.substr(0, pos_a));
   s_m = stoi(st.substr(pos_a + 1));
   e_h = stoi(et.substr(0, pos_b));
   e_m = stoi(et.substr(pos_b + 1));

   ull delta = (e_h - s_h) * 60 + (e_m - s_m);
   return delta;
}

void cal(int total_time)
{
   for (int i = 0; i < element; ++i)
   {
      if (is_inf[i])
      {
         // 完全背包
         for (int j = 0; j <= total_time - t[i]; ++j)
         {
            dp[j + t[i]] = max(dp[j + t[i]], dp[j] + c[i]);
         }
      }
      else
      {
         // 0-1背包
         for (int j = total_time; j >= t[i]; --j)
         {
            dp[j] = max(dp[j], dp[j - t[i]] + c[i]);
         }
      }
   }

   cout << dp[total_time] << endl;
}
int main()
{
   cin.sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   string i_st, i_et;
   cin >> i_st >> i_et;

   ull time = cal_time_delta(i_st, i_et);

   memset(dp, 0, sizeof(dp));
   int n;
   cin >> n;

   for (int i = 0; i < n; ++i)
   {
      int tt, cc, pp;
      cin >> tt >> cc >> pp;

      if (pp == 0)
      {
         // 无限次
         t[element] = tt;
         c[element] = cc;
         is_inf[element] = true;
         ++element;
         continue;
      }

      for (int j = 0; j < pp; ++j)
      {
         t[element] = tt;
         c[element] = cc;
         is_inf[element] = false;
         ++element;
      }
   }

   cal(time);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023年8月11日2，如有侵权请联系 cloudcommunity@tencent.com 删除