Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这道题的结果又BUG!!敬请管理员看看!!

Posted by lcmj520 at 2010-01-30 14:52:29 on Problem 1293
In Reply To:这道题的结果又BUG!!敬请管理员看看!! Posted by:lcmj520 at 2010-01-30 14:46:46
> 能AC的程序;
> 输入:
> 18 6
> 3
> 10 6 8
> 输出:
> Impossible to distribute
> 
> 不能AC的程序;
> 输入:
> 18 6
> 3
> 10 6 8
> 输出:
> 2 1 3
> 
> 但我们人为判断,不能AC的程序输出地结果才是正确的

注意,本题本人用DP,是经典的装箱问题算法。
参考代码:(不能AC的)
#include <iostream>
#include <vector>//记录巧克力包的编号,然后反向输出
#define MAX 1001
using namespace std;

int M,L,N,sum,local,box[MAX];
short int fp[MAX],fn[MAX];
int address[MAX];//记录当前使用了哪个编号的巧克力包,等会要输入到vector中
vector<int> v;

void init()
{
	int i;
	sum=0;
	scanf("%d",&N);
	for(i=1;i<=N;i++) { scanf("%d",&box[i]);sum+=box[i]; }
}

bool solve()
{
	int i,j,k;
	memset(fp,0,sizeof(fp));
	memset(fn,0,sizeof(fn));
	memset(address,0,sizeof(address));
	fp[0]=1;
        /*动态规划,装箱问题的算法*/
	for(i=1;i<=N;i++)
	{
		for(j=box[i];j<=M;j++)
		{
			if(fp[j-box[i]] && !fp[j]) { fn[j]=1;address[j]=i; }
		}
		for(k=1;k<=M;k++) fp[k]=fn[k];
	}
	for(i=M;i>0;i--)
		if(fp[i]) break;
	local=i;
	return (sum-local<=L);
}

void output()
{
	int i,t=0;
	i=local;
	v.clear();
	while(i>0)
	{
		v.push_back(address[i]);
		i-=box[address[i]];
		t++;
	}
	printf("%d",t);
	vector<int>::iterator it,start=v.begin();
	for(it=v.end();it>start;it--)
	{
		printf(" %d",*(it-1));
	}
	printf("\n");
}

int main(int argc, char* argv[])
{
	while(scanf("%d%d",&M,&L) , M&&L)
	{
		init();
		if(sum<=M+L)
		{
			if(solve())
			{
				output();
			}
			else printf("Impossible to distribute\n");
		}
		else printf("Impossible to distribute\n");
	}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator