这是一道难度标记为: 普及+/提高 的题目,主要考察了 背包问题。
仔细看看,这道题和开心的金明很相似(开心的金明为01背包问题)
但这道题增加了主物件这一设定,如果不买主物件,附属品都无法购买!
说白了就是一道依赖背包问题!
一样物品最多能出现2个附属品,这样就好办了,五种可能性:
- 啥都不买。
- 只买主件。
- 买主件和附属品1
- 买主件和附属品2
- 全都买。
只需要将 01背包代码 改一下就能做这道题了。
解题步骤
全局变量定义
typedef pair<int, int> pai; // 附属物品的两个值
struct node
{
int value; // 价值数
int prior; // 优先级
vector<pai> auxil; // 附属物
} a[MAXN];
int f[MAXN]; // dp 数组
使用 自定义结构体 + Pair 储存数据非常简洁(不喜欢太多数组)
另外最好把 Vector 改成普通数组,毕竟只有两个附属品。
数据输入
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int v, p, q;
cin >> v >> p >> q;
if (!q)
{
a[i].value = v;
a[i].prior = v * p;
}
else
{
a[q].auxil.push_back(make_pair(v, v * p));
}
}
前面的都很简单,后面的判断主要用于检查是否为附属品,如果是附属品则放到主件的 auxil 下,这样最终遍历时只需要遍历主件。使用 Pair 存放附属品值,非常的方便!
状态转移方程式
// 只购买主件
f[j] = max(f[j], f[j - a[i].value] + a[i].prior);
// 主件 + 附属品1
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first)] + a[i].prior + a[i].auxil[0].second);
// 主件 + 附属品2
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[1].second);
// 主件 + 附属品1 + 附属品2
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[0].second + a[i].auxil[1].second);
在写转移方程式前注意判断剩余金额和附属品是否存在的问题。
完整代码
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
#define MAXN 100001
typedef pair<int, int> pai;
struct node
{
int value; // 价值数
int prior; // 优先级
vector<pai> auxil; // 附属值
} a[MAXN];
int f[MAXN];
int main(int argc, char const *argv[])
{
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int v, p, q;
cin >> v >> p >> q;
if (!q)
{
a[i].value = v;
a[i].prior = v * p;
}
else
{
a[q].auxil.push_back(make_pair(v, v * p));
}
}
for (int i = 1; i <= m; i++)
{
for (int j = n; j >= 0; j--)
{
if (j >= a[i].value)
{
f[j] = max(f[j], f[j - a[i].value] + a[i].prior);
}
if (a[i].auxil.size() >= 1)
{
if (j >= (a[i].value + a[i].auxil[0].first))
{
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first)] + a[i].prior + a[i].auxil[0].second);
}
}
if (a[i].auxil.size() >= 2)
{
if (j >= (a[i].value + a[i].auxil[1].first))
{
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[1].second);
}
}
if (a[i].auxil.size() >= 2)
{
if (j >= (a[i].value + a[i].auxil[0].first + a[i].auxil[1].first))
{
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[0].second + a[i].auxil[1].second);
}
}
}
}
cout << f[n] << endl;
return 0;
}
文章写的不错,加油~