【洛谷P1858】多人背包

题目大意:求解 0-1 背包前 K 优解的和。

题解:首先,可知对于状态 \(dp[j]\) 来说,能够转移到该状态的只有 \(dp[j],dp[j-w[i]]\)。对于 K 优解来说,只需对状态额外增加一个维度即可。接着,考虑状态转移的过程,即:需要从 \(dp[j][1...k]\rightarrow dp[j][1...k],dp[j-w[i]][1...k]\rightarrow dp[j][1...k]\),可以考虑每次取出两堆数中的最大值进行比较,取较大的给当前状态,时间复杂度较高。可以发现,对于两个状态序列来说,\(dp[j][k-1]>dp[j][k]\) ,即:每个状态序列是单调递减的,可以考虑采用双指针遍历方法,时间复杂度较低。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=210;
const int maxv=5010; inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
} int n,m,K,dp[maxv][51],v[maxn],w[maxn];
int tmp[51]; void read_and_parse(){
K=read(),m=read(),n=read();
for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
memset(dp,0xcf,sizeof(dp));
dp[0][1]=0;
} void solve(){
for(int i=1;i<=n;i++)
for(int j=m;j>=w[i];j--){
int x=1,y=1,tot=0;
while(tot<=K){
if(dp[j][x]>dp[j-w[i]][y]+v[i])tmp[++tot]=dp[j][x++];
else tmp[++tot]=dp[j-w[i]][y++]+v[i];
}
for(int k=1;k<=K;k++)dp[j][k]=tmp[k];
}
long long ans=0;
for(int i=1;i<=K;i++)ans+=dp[m][i];
printf("%lld\n",ans);
} int main(){
read_and_parse();
solve();
return 0;
}
上一篇:Asp.Net Design Pattern Studynotes -- Part1


下一篇:java.util.concurrent BlockingQueue详解