boolex @ 2022-05-19 13:04:24
//看的题解的思路,大概就是说,先把同属于一个组里的东西先进行01背包,然后得到从主件花费到n的这么一个数组,然后再把这个数组往总的dp数组里放
#include<bits/stdc++.h>
using namespace std;
int n, m;
struct node
{
int v;
int w;
};
vector<node>h[65];
int dp[32005],f[32005], ff[32005];
int main()
{
int v,p,q;
node x;
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v,&p,&q);
x.v=v;
x.w=v*p;
if(q==0) h[i].push_back(x);//主件就入自己的队
else h[q].push_back(x);//附件就入主件的队
}
for(int i=1;i<=m;i++)
{
if(h[i].size()==0) continue;//如果不存在以i为主件的数组,continue
int vv=h[i][0].v;//0号是主件,vv是主件的体积(本题中为价钱)
int ww = h[i][0].w;//主件的重要性
int num=h[i].size()-1;//附件的数量
///cout<<vv<<" "<<ww<<" "<<num<<endl;//应该是没问题
//h[i][j]表示以i为主件的物品的所有附近,其中h[i][0]就是主件自己
//我要先对每个附件组进行dp,然后得出从0到V-c[i]的所有对应的值,即f'[0..V-c[i]]
//要先对除了主件以外的附件进行01背包,否则主件的体积会被算好几遍,然后最后都要加上主件的价值和重要度,
memset(f, 0, sizeof(f));
memset(ff, 0, sizeof(ff));
for(int j = 1; j<=num; j++)//对所有的附件进行01背包
for(int k = n-vv; k>=h[i][j].v;k--){
f[k] = max(f[k], f[k-h[i][j].v]+h[i][j].w);
///cout<<f[k];
}
//加上主件的价格和价值
for(int j = 0; j<=n-vv; j++){//ff[0]就是只买主件
ff[j+vv] = f[j]+ww;//游标就是他的花费,函数值就是他的重要度
///cout<<ff[j+vv];
}
///cout<<ff[1199]<<" ";应该也没问题
//再放进到真正的背包里
//小于vv的就相当于啥也没放
//一共有从vv到n个物品
for(int k = n; k>=vv; k--)//这里还是有分组背包的感觉,就是ff中的这些数是互相冲突的,只能放一个,所以外层for先写容量
for(int j = vv; j<=n; j++)//依赖背包就是把附件主件这些,转化成了m-vv+1个物品(加的那个1就是只买主件的情况)
if(k>=j)dp[k] = max(dp[k], dp[k-j]+ff[j]);
//cout<<dp[n]<<endl;
}
printf("%d",dp[n]);
return 0;
}
by 阿丑 @ 2022-05-19 16:47:41
@boolex
for(int k = n; k>=vv; k--)
for(int j = vv; j<=n; j++)
这个循环中的语句可以认为执行了
事实上这题有特殊性:
他还从因特网上查到了每件物品的价格(都是
10 元的整数倍)。
可以借此优化。
by boolex @ 2022-05-19 17:02:45
已经解决了,即背包九讲中P02“一个简单有效的方法”,把价格不同,而重要性一样的物品只保留一件,核心代码如下
fffsize = 0;
for(int j = vv-1; j<=n; j++)//细节vv-1,因为第一个数是肯定要的,所以vv-上一个1就可以把这个数也带进来。相当于一个没有附件的物品,也会被放进fff中
if(ff[j+1]>ff[j])
{
fffsize++;
fff[fffsize].v = j+1;
fff[fffsize].w = ff[j+1];
}
完整AC代码