dp之01背包hdu2639（第k优解）

http://acm.hdu.edu.cn/showproblem.php?pid=2639

题意：给出一行价值，一行体积，让你在v体积的范围内找出第k大的值.......（注意，不要和它的第一题混起来，它第一行是价值，再是体积）

思路：首先dp[i][j]代表的是在体积为i的时候第j优解为dp[i][j]......那么，我们就可以这样思考，i对应体积，那么如果只是一维的dp[i]，代表的应该是体积为i时的最大值，那么同理，dp[i][1]代表的是体积为i时的最大值，那么我们就可以退出两种动态，dp[i][m],dp[i-s[i][0]][m]+s[i][1].....然后把这两种状态开个两个数组分别保存起来，再合并出体积为i时的前k优解......依次后推，直到dp[v][k].......

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

#define max(x,y) x>y? x:y

typedef int ss;

ss dp[1005][100],s[1005][2];

ss a[50],b[50];

int main()

{

	int text;

	scanf("%d",&text);

	while(text--)

	{

		ss n,v,k;

		scanf("%d%d%d",&n,&v,&k);

		for(ss i=1;i<=n;i++)

		scanf("%d",&s[i][1]);

		for(ss i=1;i<=n;i++)

		scanf("%d",&s[i][0]);

		memset(dp,0,sizeof(dp));

		if(k==0)

		{

			printf("0\n");

			continue;

		}

		for(int i=1;i<=n;i++)

		{

			for(int j=v;j>=s[i][0];j--)

			{

				for(int m=1;m<=k;m++)

				{

					a[m]=dp[j][m];

					b[m]=dp[j-s[i][0]][m]+s[i][1];

				}

				int x=1,y=1,w=1;

				a[k+1]=b[k+1]=-1;  //这个地方要注意，因为有可能a或者b数组先比较完 

				while(w<=k&&(x<=k||y<=k))

				{

					if(a[x]>b[y])

					{

						dp[j][w]=a[x++];

					}

					else

					{

						dp[j][w]=b[y++];

					}

					if(w==1||dp[j][w]!=dp[j][w-1])       //这是去重.....

					w++;

					//printf("111\n");

				}

			}

		}

		//for(int i=1;i<=k;i++)

	printf("%d\n",dp[v][k]);

	}

	return 0;

}

巴特西

dp之01背包hdu2639（第k优解）

最新文章

热门文章