金明的预算方案

题目 金明的预算方案

思路分析

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

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

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

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

代码实现

#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