题目描述
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。
更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。
今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:
QQ截图20190313024710.png
如果要买归类为附件的物品,必须先买该附件所属的主件。
每个主件可以有0个、1个或2个附件。
附件不再有从属于自己的附件。
金明想买的东西很多,肯定会超过妈妈限定的N元。
于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。
他还从因特网上查到了每件物品的价格(都是10元的整数倍)。
他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,…,jk,则所求的总和为:
v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk](其中*为乘号)
请你帮助金明设计一个满足要求的购物单。
样例
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
2200
其实,,只要把这道题前面那道有依赖的背包问题 做了,这道题就是那道题的降维版本,而且在提高课的目录里,这道题还在那道题之后,,
y总为啥视频里说不能01背包做呢,,,
看视频的时候顿时有种y总失忆了的赶脚hhh
https://www.acwing.com/problem/content/10/
好的不说废话了,上思路,
思路就是对于每个组(题目中给定的森林里面的每棵树),,分为 两种情况 选和不选 根节点
1.选根节点,然后用根之下的每一个子节点01背包去更新,
每个子节点作为一个物品做01背包去更新 等价于 枚举每个子节点选和不选就更新
这个例子就好比 我们看到的01背包算法和 暴力2的n次方枚举
我们规定m为背包总体积
当然 这里能更新的体积只有0~m-fv
因为选子节点必须选根节点,所以说m-fv-m是不能更新的,只不过我们是最后在把根节点的价值加上去的,
加上去之后 再和 当前这棵树做01背包之前的数组比较 各自取最大,
参考代码:
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=80,M=32010;
int f[M],g[M];
int h[N],e[N],ne[N],idx;
void add(int a,int b){
e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}
struct obj{
int v;
int p;
int q;
};
obj a[N];
int m,n;
int main(){
cin>>m>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
int v,p,q;
cin>>v>>p>>q;
a[i]={v,p,q};
if(!q)continue;
else{
add(q,i);
}
}
for(int i=1;i<=n;i++){
if(a[i].q==0){
memcpy(f,g,sizeof g);
int fv=a[i].v;
for(int j=h[i];~j;j=ne[j]){
int son=e[j];
int v=a[son].v;int p=a[son].p;
for(int k=m-fv;k>=v;k--){
f[k]=max(f[k],f[k-v]+v*p);
}
}
for(int j=m;j>=fv;j--)f[j]=f[j-fv]+a[i].v*a[i].p;
for(int j=fv-1;j>=0;j--)f[j]=0;
for(int j=m;j>=0;j--){
g[j]=max(g[j],f[j]);
}
}
}
cout<<g[m]<<endl;
}