---
title: "金明的预算方案"
created: 2025-11-28
tags:
  - 算法
---

# 金明的预算方案

## 题目 [金明的预算方案](https://www.acwing.com/problem/content/489/)

![[image-5c5bfefd.png]]

## 思路分析

![[image-17d84b4e.png]]

我的想法是 延用之前某道按日期做背包的思路 固定每组物品就4种选法 有就给价值 没有价值就为0 这样的话 就无需考虑每组物品到底有多少附件

相关的题解都是 使用二进制的方式 有多少件物品 就左移多少位 从而考虑到所有组合 这种方式会更灵活  尤其是附件比较多的情况下

但是这里题目说了 只有最多俩附件 且附件不再有附件 感觉我的想法是可行的

但还是得分开存储主件和附件 因为同一组并不是一起输入的 而是靠p标识

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef pair<int,int> PII;
const int N=60,M=32010;
int n,m;
int f[N][M];//前i组物品中选 总价值不超过j的所有选法 属性max
PII master[N];
vector<PII> servent[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(!q) master[i]={v,p};
        else servent[q].push_back({v,p});
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            for(int k=0;k<1<<servent[i].size();k++){
                int v=master[i].first,p=master[i].second;
                for(int u = 0 ; u < servent[i].size() ; u++){
                    if((k >> u) & 1){
                        v += servent[i][u].first;
                        p += servent[i][u].second;
                    }
                }
                if(j >= v)
                    f[i][j] = max(f[i][j], f[i-1][j-v] + p);
            }
        }
    }
    cout<<f[n][m];
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[机器分配|机器分配]] 🏠 [[00-冲刺国赛]] ➡️ [[状态机dp|状态机dp]]