www.rqnoj.cn/Problem_123.html
这道题目实际上意思就是求前K优解，效仿一般的动态规划，可以很方便的搞定这个。。只是转移的时候更新的是一个队列。。
Code：

#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)const int maxk=50+1,maxv=5000+1,maxn=200,inf=~0U>>1;using namespace std;int k,v,n;struct Thing{ int w,v;}T[maxn];int tmp[maxk];struct State{ int n,A[maxk]; State(){n=0;} void put(int x){A[n++]=x;} void Update(State&s,int v) { int m=min(k,s.n+n),i=0,j=0; #define get(i) (s.A[i]+v) A[n]=-inf;s.A[s.n]=-inf; rep(o,m) { if(A[i]>get(j)) tmp[o]=A[i],i++; else tmp[o]=get(j),j++; } memcpy(A,tmp,sizeof(int)*m); n=m; }}Dp[maxv];void Init(){ scanf("%d%d%d",&k,&v,&n); rep(i,n)scanf("%d%d",&T[i].w,&T[i].v);}void Solve(){ Dp[0].put(0); rep(i,n) { for(int j=v;j>=T[i].w;j–) Dp[j].Update(Dp[j-T[i].w],T[i].v); } int ans=0; rep(i,Dp[v].n)ans+=Dp[v].A[i]; cout<<ans<<endl;}int main(){ //freopen("in","r",stdin); Init(); Solve();}