[洛谷] P1064 金明的预算方案

mr小卓X

September 1, 2020

1059views

One comment

3215 words

算法

这是一道难度标记为: 普及+/提高 的题目，主要考察了 **背包问题**。

仔细看看，这道题和开心的金明很相似（开心的金明为01背包问题）

但这道题增加了主物件这一设定，如果不买主物件，附属品都无法购买！

说白了就是一道**依赖背包问题**！

一样物品最多能出现2个附属品，这样就好办了，五种可能性：

1. 啥都不买。
2. 只买主件。
3. 买主件和附属品1
4. 买主件和附属品2
5. 全都买。

只需要将 **01背包代码** 改一下就能做这道题了。

## 解题步骤

### 全局变量定义

```cpp
typedef pair<int, int> pai; // 附属物品的两个值

struct node
{
    int value;         // 价值数
    int prior;         // 优先级
    vector<pai> auxil; // 附属物
} a[MAXN];

int f[MAXN]; // dp 数组
```
使用 自定义结构体 + Pair 储存数据非常简洁（不喜欢太多数组）
另外最好把 Vector 改成普通数组，毕竟只有两个附属品。

### 数据输入

```cpp
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 存放附属品值，非常的方便！

### 状态转移方程式

```cpp
// 只购买主件
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);
```

在写转移方程式前注意判断剩余金额和附属品是否存在的问题。

### 完整代码

```cpp
#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;
}
```

Last modification：September 2nd, 2020 at 07:40 pm

如果觉得我的文章对你有用，请随意赞赏

[洛谷] P1064 金明的预算方案