这题可以考虑将主件与其附件的组合进行01背包问题的做法 从而获得主件与其附件组合的最大价值 然后再以其组合进行依次01背包问题的解法
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=32000+10;
const int M=60+10;
int h[N]; //存放分组完后的 主件和附件的组合
int f[N]; //存放花费i元的状态数
int v[M],p[M],q[M]; //v[]表示第i件的价格,p[]表示重要程度,q[]表示主附件的从属关系
int s[M]; //存放v[]*p[]
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v[i],&p[i],&q[i]);
s[i]=v[i]*p[i];
}
for(int i=1;i<=m;i++)
{
if(q[i]==0) //如果是主件的进行主件与附件的组合处理
{ //因为必须要有主件才可以有附件 所以直接从主件开始处理就可以了
memset(h,0,sizeof h);
for(int j=v[i];j<=n;j++) //先对一个主件的情况先单独处理
h[j]=f[j-v[i]]+s[i];
for(int j=1;j<=m;j++) //判断该主件是否存在附件
{
if(q[j]==i) //如果存在 对附件组合进行枚举
for(int k=n;k>=v[i]+v[j];k--) //由于附件是与主件组合 所以要加上主件的价格
h[k]=max(h[k],h[k-v[j]]+s[j]);
}
for(int j=v[i];j<=n;j++)
f[j]=max(f[j],h[j]); //选择上述枚举完成后的最大情况
}
}
cout<<f[n];
return 0;
}
大佬,请问为什么一定要用额外数组进行计算最后再比较大小, 而我如果直接用f数组的话就WA掉了???
就是你定义了一个h数组我没有用直接用f数组就WA掉了
因为这题的思路是先求出主件+附件组合的价值 所以要用一个h数组去保存 而如果你直接用一个f数组的话 根据题目如果要选附件的前提必须先选主件 如果直接用f数组就无法保证每个选取每个附件之前都已经选取了相应的主件
明白了谢谢大佬