hdoj2159 二维背包

题目链接
练了下二维背包,有了新的收获。这道题求出是否达到经验值不难,用二维背包求出最大经验值即可,但是我不知道如何得到达到经验值时,花掉的最少忍耐度。。看了下discuss,发现其实只要从0到m找一下最小的使之达到过关经验值的忍耐度即可。

#include<stdio.h>
int f[102][102];
int main()
{
	int n,m,k,s;
	while(scanf("%d %d %d %d",&n,&m,&k,&s)!=EOF)
	{
		int i,j,t;
		int v[102],c[102],b[102];
		for(i=1;i<=k;i++)
		{
			scanf("%d %d",&v[i],&c[i]);
			b[i]=1;
		}
		for(j=0;j<=m;j++)
			for(t=0;t<=s;t++)
				f[j][t]=0;
		int sum=0;
		for(i=1;i<=k;i++)
			for(j=0;j<=m;j++)
				for(t=0;t<=s;t++)
				{
					if(c[i]<=j && b[i]<=t)
					{
						if(f[j-c[i]][t-b[i]]+v[i]>f[j][t])
							f[j][t]=f[j-c[i]][t-b[i]]+v[i];
						else
							f[j][t]=f[j][t];
					}
					else
						f[j][t]=f[j][t];
				}
		if(f[m][s]>=n)
		{
			for(i=0;i<=m;i++)		//找到最小的用去忍耐度,使达到过关经验值
				if(f[i][s]>=n)
				{
					printf("%d\n",m-i);
					break;
				}
		}
		else
			printf("-1\n");
	}
return 0;

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>