AcWing 487. 金明的预算方案

#include 
#include 
#include 
#include #define v first
#define w second
using namespace std;
typedef pairint, int> PII;
const int N = 60, M = 32010;
int n, m;
PII master[N];
vector servent[N];
int f[M];
int main() {
    cin >> m >> n;//m总钱数  n个数 
    for (int i = 1; i  ) {
        int v, p, q;
        cin >> v >> p >> q;
        p *= v;//价值 
        if (!q) master[i] = {v, p};//如果是0，表示为主件 
        else servent[q].push_back({v, p});//如果不是0，为附件，插入相关主键 
    }
    for (int i = 1; i //个数 
        for (int u = m; u >= 0; u -- ) {//总钱数 
            for (int j = 0; j 1  )
            //转换为二进制，对于每个主件，有几种选法 
             {
                int v = master[i].v, w = master[i].w;
                for (int k = 0; k  )
                    if (j >> k & 1)
                    {//如果第k位是1，那就说明选第k个 
                        v += servent[i][k].v;
                        w += servent[i][k].w;
                    }
                if (u >= v) f[u] = max(f[u], f[u - v] + w);
            }
        } 
    cout  endl;
    return 0;
}

#include
#include#define v first
#define w second
using namespace std ;
typedef pairint,int>PII;
const int N=32100;
int f[N];
int n,m;
vectorservent[N];
PII master[N];
int main()
{
    cin>>m>>n;
    for(int i=1;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)
        for(int j=m;j>=0;j--)
            for(int k=0;k1)
            {
                int w=master[i].w,v=master[i].v;
                for(int u=0;u)
                {
                    if(k>>u&1)
                    {
                        w+=servent[i][u].w;
                        v+=servent[i][u].v;
                    }
                }
                if(j>=v)
                    f[j]=max(f[j],f[j-v]+w);
            }
    coutendl;
    return 0;
}