学步园

第K大背包问题

现在01的基础上多加一维，dp[v][k]，表示在v下第k大的价值。。。

用A[ ],B[ ];分别记录加入第i件物品的前k个最大价值，不加入第i件物品的前k个最大价值

取两个数组的前k大值

也可以用一个数组存，再排序，找前k项

#include<stdio.h>
#include<string.h>
int dp[1010][40];
int main()
{
	int i,m,n,V[110],W[110],j,k,A[40],B[40],t,a,b,c,v;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&v,&k);
		for(i=0;i<n;i++)
			scanf("%d",&W[i]);
		for(i=0;i<n;i++)
			scanf("%d",&V[i]);
		memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++)
			for(j=v;j>=V[i];j--)
			{
				for(m=1;m<=k;m++)
				{
					A[m]=dp[j-V[i]][m]+W[i];
					B[m]=dp[j][m];
					
				}
				A[m]=B[m]=-1;
				a=b=c=1;
				while(c<=k&&(a!=m||b!=m))
				{
					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]);
	}
	return 0;
}