P1858 多人背包
时间:2021-12-13 作者:0-SmartBig-0
# 原题链接 :
->https://域名.cn/problem/P1858<-
# 题外话 :
好像许多题解区 daolaos 都引用了背包九讲里面的一些很抽象的语言,题解区第一的 dalao 用了所谓“刷表”方式证明。也很模糊。本题解重讲思路。
# 思路 :
此题大致同于 01 背包;
重点在:
/*核心代码*/ for(int i=1;i<=n;i++) { for(int j=m;j>=v[i];j--) { int add=0,a=1,b=1; while(add<=k) { if(f[j][a]>f[j-v[i]][b]+w[i]) { x[++add]=f[j][a++]; } else { x[++add]=f[j-v[i]][b++]+w[i]; } } for(int t=1;t<=k;t++) f[j][t]=x[t]; } }
其中 $ f[i][j] $ 表示前 i 个数据最 j 优解;
$ add $ 表示到第几个优解了 , 所以只要 $ add\le k $ 都可进入状态转移;
$ x[i] $ 记录当前否被以前的替换掉 ( 此处如 01 背包 ),所以之后还要把 x 里的值刷回去;
a 与 b 分别记录现在、前面的优解;
就优解判断否被更新。
# 完整CODE:
#include<bits/stdc++.h> #define int long long using namespace std; int f[5001][101],v[10001],w[100001],x[100001]; signed main() { int k,m,n; cin>>k>>m>>n; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; } memset(f,~0x3f3f3f3f,sizeof(f)); f[0][1]=0; for(int i=1;i<=n;i++) { for(int j=m;j>=v[i];j--) { int add=0,a=1,b=1; while(add<=k) { if(f[j][a]>f[j-v[i]][b]+w[i]) { x[++add]=f[j][a++]; } else { x[++add]=f[j-v[i]][b++]+w[i]; } } for(int t=1;t<=k;t++) f[j][t]=x[t]; } } int sum=0; for(int i=1;i<=k;i++) sum+=f[m][i]; cout<<sum<<\'\n\'; return 0; }