完全背包，不过尔尔

昨天就搞了一个题，悲剧啊，不过昨晚上学长又给我们讲了普利姆算法，感觉收获挺大的，嘿嘿，今天争取用代码实现，昨天上自习课的时候，突然想到自己貌似有很多方面还是完全没有涉及，今天一定要汇总一下，这样才能有一个目标，昨晚上管理员已在群里表明下个月会踢人，我的现状，岌岌可危啊……

下面总结自己昨日的收获：

题目： 完全背包

原题地址：请猛击

时间：2535ms

 
#include<stdio.h>
#include<string.h>
int bag[50005],zhong[50005];//要标记空间哦
void dp(int v,int c,int w)
{
	for(int i=1;i<=v;i++)
	{
		if(i>=c&& i==zhong[i-c]+c && (w+bag[i-c])>bag[i] && w+bag[i-c]!=bag[i-1])
		{
			zhong[i]=i;                           //大小必须等于空间大小
			bag[i]=w+bag[i-c];
		}
	}
}
int main()
{
	int n,v,i,j,c,w,a;
	scanf("%d",&a);
	while(a--)
	{
		scanf("%d%d",&n,&v);
		memset(bag,0,sizeof(bag));
		memset(zhong,0,sizeof(zhong));
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&c,&w);
			dp(v,c,w);
		}
		if(bag[v]==0)
			printf("NO\n");
		else
			printf("%d\n",bag[v]);
	}
	return 0;
}        

虽然一次就AC了，但是时间明显有点长，后来看了看队友的代码，表示膜拜！！

时间：1432ms

 
 
#include<stdio.h>
#include<algorithm>
#include<string.h>
struct sb
{
	int x,y;
}ok[2005];
bool cmp(struct sb t1,struct sb t2)
{
	return t1.x<t2.x; 
}
int main()
{
	int a,b,n,m,v,q;
	scanf("%d",&q);
	while(q--)
	{
		int yi[50001]={0};
		memset(yi,-999999,sizeof(yi));
		yi[0]=0;
		scanf("%d%d",&n,&v);
		for(a=1;a<=n;a++)
			scanf("%d%d",&ok[a].x,&ok[a].y);
		std::sort(ok+1,ok+n+1,cmp);
		for(b=1;b<=n;b++)
		{
			for(m=ok[b].x;m<=v;m++)
			{
				
					if(yi[m]<(yi[m-ok[b].x]+ok[b].y))
						yi[m]=yi[m-ok[b].x]+ok[b].y;
				
			}
		}
		if(yi[v]>0)
		    printf("%d\n",yi[v]);
		else
			printf("NO\n");
	}
}
                

终于把课给选上了！！开始新的一天了，加油！！