其实我一直觉得这道题还有除分组背包的解法
题目描述
如果要买归类为附件的物品,必须先买该附件所属的主件。
每个主件可以有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
C++ 代码
//在以i为根的树中花费j元所得的最大价值
#include<bits/stdc++.h>
#define N 100
using namespace std;
int n,m;
int price[N],imp[N],bel;
int f[N][N*N];
bool v[N];
vector<int>son[N];
inline void dp(int x){
for (int i=0;i<=price[x];i++) f[x][i]=0;
for (int k=0;k<son[x].size();k++){
int v=son[x][k];
dp(v);
for (int t=m;t>=price[v];t--)
for (int j=t;j>=price[v];j--)
f[x][t]=max(f[x][t],f[x][t-j]+f[v][j]);
}
if(x!=0) for (int i=m;i>=price[x];i--) f[x][i]=f[x][i-price[x]]+imp[x];
}
inline void putin(){
int flag=0;
scanf("%d%d",&m,&n);m/=10;
for (int i=1;i<=n;i++){
scanf("%d%d%d",&price[i],&imp[i],&bel);
price[i]/=10;
if(price[i]%10>0) flag=1;
imp[i]*=price[i];
son[bel].push_back(i);
}//仔细读题发现,其实价格都是整十,于是可以在此基础上/10,甚至/100
memset(f,0xcf,sizeof(f));
if(flag==0){
m/=10;
for (int i=1;i<=n;i++) price[i]/=10;
}
}
int main(){
putin();
dp(0);
printf("%d\n",f[0][m]*10);
return 0;
}
所以这道题不能这么做,这也是为什么依赖关系只有一层的缘故
这样不对吧,时间复杂度是$O(mn^2)$的,能过是因为数据弱,物品价格都是10甚至100的倍数
大佬,这时间复杂度是多少,为啥不会超时?
%%%tql