明天 2023 CSP 了，简单写写，以后在补吧。
题目描述
给你若干个物品，每个物品有体积 \(t_i\)，价值 \(c_i\)，每个物品可以拿 \(p_i\) 次。特别的，当 \(p_i=0\) 的时候，这个物品可以取无数次。
具体思路
solution 1：朴素背包
-
对于 \(p_i=0\) 的物品，我们可以看成一个完全背包。
-
对于 \(p_i \ne 0\) 的物品，我们可以在 01 背包的基础上多枚举一个 \(k\)，表示当前第 \(i\) 个物品取多少个。
时间复杂度：\(O(nv \max \limits_{i \in [1,n]} \{ p_i \})\)
Code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e3+5,D=10;
int t[N],c[N],p[N],f[M];
char st[D],ed[D];
int get(int l,int r,char *s){
int res=0;
for(int i=l;i<=r;i++){
res=res*10+(s[i]-'0');
}
return res;
}
int main(){
int minx,secx,miny,secy,n,v;
scanf("%s%s%d",st+1,ed+1,&n);
for(int i=1;i<=strlen(st+1);i++){
if(st[i]==':'){
minx=get(1,i-1,st);
secx=get(i+1,strlen(st+1),st);
}
}
for(int i=1;i<=strlen(ed+1);i++){
if(ed[i]==':'){
miny=get(1,i-1,ed);
secy=get(i+1,strlen(ed+1),ed);
}
}
v=(miny*60+secy)-(minx*60+secx);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&t[i],&c[i],&p[i]);
}
for(int i=1;i<=n;i++){
if(!p[i])
for(int j=t[i];j<=v;j++)
f[j]=max(f[j],f[j-t[i]]+c[i]);
else
for(int j=v;j>=t[i];j--)
for(int k=1;k<=p[i];k++)
if(j-k*t[i]>=0)
f[j]=max(f[j],f[j-k*t[i]]+k*c[i]);
}
int ans=0;
for(int i=0;i<=v;i++){
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
solution 2：二进制拆分（优化）
我们发现，上面枚举次数 \(k\) 的行为实际上是将第 \(i\) 个物品拆成 \(p_i\) 个次数为 \(1\) 的物品，每个物品体积和价值分别是 \(t_i,c_i\)。
但这样有可能会超时（上面的代码由于数据水所以也过了）。
因此我们发明了二进制拆分。
众所周知，任何一个数都可以用二进制来表示，那么我们现在将第 \(i\) 个物品拆成 \(\log p_i\) 个次数分别为 \(1,2,4,\ldots\) 的物品，每个物品的体积分别是 \(t_i,2t_i,4t_i,\ldots\)，价值分别为 \(c_i,2c_i,4c_i,\ldots\)。
那么对于完全背包，我们就不用管次数了，一直拆分直到 \(2^k t_i>v\)。
时间复杂度：\(O(nv \max \limits_{i \in [1,n]} \{ \log p_i \})\)
Code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+5,D=10;
int t[N],c[N],p[N],f[M];
int a[M],w[M],cnt;
char st[D],ed[D];
int get(int l,int r,char *s){
int res=0;
for(int i=l;i<=r;i++){
res=res*10+(s[i]-'0');
}
return res;
}
int main(){
int minx,secx,miny,secy,n,v;
scanf("%s%s%d",st+1,ed+1,&n);
for(int i=1;i<=strlen(st+1);i++){
if(st[i]==':'){
minx=get(1,i-1,st);
secx=get(i+1,strlen(st+1),st);
}
}
for(int i=1;i<=strlen(ed+1);i++){
if(ed[i]==':'){
miny=get(1,i-1,ed);
secy=get(i+1,strlen(ed+1),ed);
}
}
v=(miny*60+secy)-(minx*60+secx);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&t[i],&c[i],&p[i]);
if(p[i]){
int k=0;
while(p[i]>=(1<<k)){
cnt++;
a[cnt]=t[i]*(1<<k);
w[cnt]=c[i]*(1<<k);
p[i]=p[i]-(1<<k);
k++;
}
if(p[i]){
cnt++;
a[cnt]=t[i]*p[i];
w[cnt]=c[i]*p[i];
}
}
else{
int k=0;
while(t[i]*(1<<k)<=v){
cnt++;
a[cnt]=t[i]*(1<<k);
w[cnt]=c[i]*(1<<k);
k++;
}
}
}
for(int i=1;i<=cnt;i++){
for(int j=v;j>=a[i];j--){
f[j]=max(f[j],f[j-a[i]]+w[i]);
}
}
int ans=0;
for(int i=0;i<=v;i++){
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}