现在的位置: 首页 > 综合 > 正文

【POJ3628】Bookshelf 2 01背包,水题

2016年09月22日 ⁄ 综合 ⁄ 共 414字 ⁄ 字号 评论关闭

就是在说给你几种物品,然后做01背包,不比它给出的B小的第一个状态是多少。

直接看代码吧,太水了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 25
#define M 1001000
using namespace std;
int n,m;
bool f[M];
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,p,a,b;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(f,0,sizeof(f));
		f[0]=1;
		p=0x3f3f3f3f;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a);
			for(j=m-1;j>=0;j--)if(f[j])
			{
				if(j+a<m)f[j+a]=1;
				else p=min(p,j+a-m); 

			}
		}
		printf("%d\n",p);
	}
	
	return 0;
}

抱歉!评论已关闭.