混合背包问题是把01背包、完全背包、多重背包混在一起的问题,看着比较复杂,其实就是分而治之,转换为前面这三种背包问题即可。
看题:
樱花
题目背景
《爱与愁的故事第四弹·plant》第一章。
题目描述
爱与愁大神后院里种了
输入格式
共
第 hh:mm
,其中
第
输出格式
只有一个整数,表示最大美学值。
样例 #1
样例输入 #1
6:50 7:00 3
2 1 0
3 3 1
4 5 4
样例输出 #1
11
提示
样例解释:赏第一棵樱花树一次,赏第三棵樱花树
通用解题思路
只要按照以下思路去解题即可:
for (循环物品种类) {
if (是 0 - 1 背包)
套用 0 - 1 背包代码;
else if (是完全背包)
套用完全背包代码;
else if (是多重背包)
套用多重背包代码;
}
具体解法
题目其实是一个多重背包+完全背包的结合。因此先把多重背包的部分,转换为0-1背包。这里可以用二进制分组进行优化(但是我代码为了省事就没写)。接着,有以下的状态转移方程:
- 完全背包的部分:
- 0-1背包的部分:
接着直接写代码就行了。
代码
#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);
}
转载请注明来源:https://longjin666.cn/?p=1757(在新窗口中打开)
欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~
![](https://pic-bed-gz-tencent.longjin666.cn/20201215120415.jpg)