[THUPC 2023 初赛] 背包

题目大意

有nnn种物品，第iii种物品体积为viv_ivi​，价值为cic_ici​。

有qqq次询问，每次给出背包的体积VVV，你可以选择若干种物品，每种物品可以选择任意多个（也可以不选），在选出物品的体积的和恰好为VVV的前提下最大化选出物品的价值的和。输出最大的价值和。如果不存在体积恰好为VVV的方案，输出−1-1−1。

VVV远大于viv_ivi​。

题解

第一步：DP

因为VVV远大于viv_ivi​，显然我们可以先放性价比最高的物品知道无法再放为止，再用性价比相对较低的物品来替换其中的一部分使得最后的体积恰好为VVV。一个物品的性价比，即civi\dfrac{c_i}{v_i}vi​ci​​。

设性价比最高的物品为kkk，我们假设这个书包放物品kkk的数量可以为实数，那么最大的价值和为ckvk×V\dfrac{c_k}{v_k}\times Vvk​ck​​×V（注意小数不能舍去）。当然，这只是假设，我们还需要用其他物品来替换。

设fjf_jfj​中的jjj表示当前选择了若干个非kkk的物品，这些物品的体积和对vkv_kvk​取模为jjj，设这些物品的体积和为ppp，价值和为qqq，则fjf_jfj​为p×ckvk−qp\times \dfrac{c_k}{v_k}-qp×vk​ck​​−q的最小值。fjf_jfj​的意义就是替换使得所有物品模vkv_kvk​为jjj后物品的总价值相对于原来放满物品kkk，其价值减少了多少。

初始值f0=0f_0=0f0​=0，其余的fff值设为极大值，转移式为

f(j+vi)%vk=min⁡(f(j+vi)%vk,fj+ci−ckvk×vi)f_{(j+v_i)\% v_k}=\min(f_{(j+v_i)\% v_k},f_j+c_i-\dfrac{c_k}{v_k}\times v_i)f(j+vi​)%vk​​=min(f(j+vi​)%vk​​,fj​+ci​−vk​ck​​×vi​)

若背包体积为ttt，如果ft%vkf_{t\%v_k}ft%vk​​的值为初始值，则输出−1-1−1；否则答案为ckvk×t−ft%vk\dfrac{c_k}{v_k}\times t-f_{t\% v_k}vk​ck​​×t−ft%vk​​，可以证明这一定是一个整数。为了方便，在计算中可以先将所有数都乘上vkv_kvk​，在最后除回来即可，不会爆long long。

不过，我们发现，如果这样做的话，你要枚举每种物品，再枚举每种状态，还要枚举这种物品放的个数，时间复杂度为O(n⋅vk2)O(n\cdot v_k^2)O(n⋅vk2​)，这样做的话会超时。

DP是要用的，不过我们可以换一种方法转移。

第二步：dijkstra

上面说到的状态转移式

f(j+vi)%vk=min⁡(f(j+vi)%vk,fj+ci−ckvk×vi)f_{(j+v_i)\% v_k}=\min(f_{(j+v_i)\% v_k},f_j+c_i-\dfrac{c_k}{v_k}\times v_i)f(j+vi​)%vk​​=min(f(j+vi​)%vk​​,fj​+ci​−vk​ck​​×vi​)

我们可以让点jjj向点((j+vi)%k)((j+v_i)\% k)((j+vi​)%k)连一条边权为ci−ckvk×vic_i-\dfrac{c_k}{v_k}\times v_ici​−vk​ck​​×vi​的边，然后在这个图上跑dijkstra即可求出所有的fff值。时间复杂度为O(n⋅vk+vklog⁡vk)O(n\cdot v_k+v_k\log v_k)O(n⋅vk​+vk​logvk​)。

code

#include
using namespace std;
int n,tq,tot=0,z[1000005],d[5000005],l[5000005],r[5000005];
long long k,ans,v[5000005],f[1000005];
struct node{long long v,c;
}w[105];
queueq;
bool cmp(node ax,node bx){return ax.c*bx.v>bx.c*ax.v;
}
long long in(){long long t=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}return t;
}
void add(int xx,int yy,long long zz){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;v[tot]=zz;
}
int main()
{n=in();tq=in();for(int i=1;i<=n;i++){w[i].v=in();w[i].c=in();}sort(w+1,w+n+1,cmp);for(int i=2;i<=n;i++){for(int j=0;jadd(j,(j+w[i].v)%w[1].v,w[1].c*w[i].v-w[i].c*w[1].v);}}for(int i=1;iint u=q.front();q.pop();z[u]=0;for(int i=r[u];i;i=l[i]){if(f[d[i]]>f[u]+v[i]){f[d[i]]=min(f[d[i]],f[u]+v[i]);if(!z[d[i]]){q.push(d[i]);z[d[i]]=1;}}}}while(tq--){k=in();if(f[k%w[1].v]==2e18){printf("-1\n");continue;}ans=(k*w[1].c-f[k%w[1].v])/w[1].v;if(ans<0) ans=-1;printf("%lld\n",ans);}return 0;
}

第三步：set

打完上面的代码，就能AC了吗？

不能，还是会TLE。

因为在用队列的时候，每个元素可能会被加入优先队列多次，这样进出队列的次数会很大，时间会增大。

所以我们不能用优先队列，但可以用set。把所有优先队列的操作改为set的操作，并保持set中没有相同的元素即可。

时间复杂度为O(n⋅vk+vklog⁡vk)O(n\cdot v_k+v_k\log v_k)O(n⋅vk​+vk​logvk​)，虽然set的常数比较大，但不会出现上面优先队列的情况。

下面是AC代码。

code

#include
using namespace std;
int n,tq,tot=0,z[1000005],d[10000005],l[10000005],r[10000005];
long long k,ans,v[10000005],f[1000005];
struct node{long long v,c;
}w[105];
struct vt{int x;long long dis;bool operator<(const vt ax)const{if(dis!=ax.dis) return diss;
bool cmp(node ax,node bx){return ax.c*bx.v>bx.c*ax.v;
}
long long in(){long long t=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}return t;
}
void add(int xx,int yy,long long zz){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;v[tot]=zz;
}
int main()
{n=in();tq=in();for(int i=1;i<=n;i++){w[i].v=in();w[i].c=in();}sort(w+1,w+n+1,cmp);for(int i=2;i<=n;i++){for(int j=0;jadd(j,(j+w[i].v)%w[1].v,w[1].c*w[i].v-w[i].c*w[1].v);}}for(int i=1;i0,0});s.insert((vt){1e9,2e18});while(s.size()>1){int u=(*s.begin()).x;s.erase(s.begin());if(z[u]) continue;z[u]=1;for(int i=r[u];i;i=l[i]){if(f[u]+v[i]set::iterator it=s.lower_bound((vt){d[i],f[d[i]]});if((*it).x==d[i]) s.erase(it);f[d[i]]=f[u]+v[i];s.insert((vt){d[i],f[d[i]]});}}}while(tq--){k=in();if(f[k%w[1].v]==2e18){printf("-1\n");continue;}ans=(k*w[1].c-f[k%w[1].v])/w[1].v;if(ans<0) ans=-1;printf("%lld\n",ans);}return 0;
}