金明的预算方案
本题可以用分组背包来做,用二进制枚举所有方案。
如何枚举每组的所有方案,并且每组只满足其中一个呢?
比方说$A$物品有附件$a$和$b$,那么所对应的所有方案就是
- A a
- A b
- A a b
我们可以发现,这样分就可以把第$i$组物品的所有方案补充不漏的枚举一遍,这时,我们恰好发现,二进制通过$0$和$1$恰好可以得到每组方案每个附件选还是不选,所以我们就可以从$0$开始由小到大枚举所有方案了。
接下来看看代码:
#include<bits/stdc++.h>
#define V first
#define W second
using namespace std;
const int M = 32010,N = 70;
typedef pair<int,int> PII;//用pair来存储体积和价值,真的是太~妙~啦~
PII master[N];//一维的主件数组
vector<PII> servant[N];//二维的附件数组(a,我就不写servent了hh)
int f[M];//f[i][j]:从前i组物品中选,总体积(钱数)不超过j的所有选法
int m,n;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
int v,w,q;
cin>>v>>w>>q;
if(!q)master[i]={v,v*w};
else servant[q].push_back({v,v*w});
}
for(int i=1;i<=n;i++)
{
if(master[i].V)//判断第i件物品是否是主件
{
for(int j=m;j>=0;j--)
{
for(int k=0;k<(1<<servant[i].size());k++)//二进制枚举所有选法,真的是太~妙~啦~
{
int v=master[i].V,w=master[i].W;//注意体积和价值一定要包含主件
for(int u=0;u<servant[i].size();u++)//枚举当前选法的每一个附件是否有被选
if(k>>u&1)//如果被选
{
auto &sv=servant[i];//也是学y总搞了一个sv好吧qwq
v+=sv[u].V;
w+=sv[u].W;
}
if(j>=v)f[j]=max(f[j],f[j-v]+w);//状态转移
}
}
}
}
cout<<f[m];
}
收工!