学步园

题目分析：参考http://hi.baidu.com/chenyun00/blog/item/f1c7ae545e9e2a491138c26b.html

第K优解问题
其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。
首先看01背包求最优解的状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。显然f[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。
然后原方程就可以解释为：f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。有序队列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是O(VNK)。

01背包再清楚不过了，主要还是是有序队列合并的问题

#include<iostream>
#include<cstdio>
using namespace std;
int dp[1100][50],w[110],v[110],A[50],B[50];
int main()
{
	int ca;
	scanf("%d",&ca);
	while(ca--)
	{
      int n,V,k,a,b,c;
	  scanf("%d %d %d",&n,&V,&k);
	  for(int i=1;i<=n;i++)
		  scanf("%d",w+i);
	  for(int i=1;i<=n;i++)
		  scanf("%d",v+i);
	  memset(dp,0,sizeof(dp));
	  for(int i=1;i<=n;i++)
		  for(int j=V;j>=v[i];j--)
		  {
			  for(c=1;c<=k;c++)
				  A[c]=dp[j][c];
			  for(c=1;c<=k;c++)
				  B[c]=dp[j-v[i]][c]+w[i];
			  A[c]=B[c]=-1;
			  a=b=c=1;
			  while(c<=k&&(A[a]!=-1||B[b]!=-1))
			  {
				  if(A[a]>B[b])
					  dp[j][c]=A[a++];
				  else
					  dp[j][c]=B[b++];
				  if(dp[j][c]!=dp[j][c-1])//防止重复
					  c++;
			  }
		  }
	printf("%d\n",dp[V][k]);
	}
	system("pause");
	return 0;
}