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

WA啊, 求助!! 简单的01背包问题, 大家帮忙看下 ,谢谢哈

Posted by caizhicong0503 at 2008-11-04 19:14:14 on Problem 3211 and last updated at 2008-11-04 19:14:52
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct WashClothes
{
	int time;
	string color;
};

bool cmp(WashClothes a, WashClothes b)
{
	if(a.color < b.color) return 1;
	else if(a.color > b.color) return 0;
	return a.time < b.time;
}

int Bag(vector<int> &p)
{
	if(p.size() == 0) return 0;
	else if(p.size() == 1) return p[0];
	bool ok[300001];
	memset(ok,0,sizeof(ok));
	ok[p[0]] = 1;
	int Max = p[0];
	int sum = p[0];
	for(int i = 1; i< p.size(); ++i)
	{
		//ok[p[i]] = 1;
		int M = Max;
		sum += p[i];
		if(p[i] > M) M = p[i];
		for(int j = 1; j<= Max; ++j)
		{
			if(ok[j] && (j+p[i])<= sum)
			{
				ok[j+p[i]] = 1;
				if(j+p[i] > M) M = j+p[i];
			}
		}
		ok[p[i]] = 1;
		
		Max = M;
	}
	int ret = max(p[0],sum-p[0]);
	for(int i = 0; i<= Max; ++i)
	{
		if(ok[i])
		{
			if(ret > max(i, sum-i))
			{
				ret = max(i, sum-i);
			}
		}
	}
	return ret ;
}

int main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)) {
		if( n == 0 && m == 0) break;
		char ss[1000];
		for(int i = 0; i< n; ++i) scanf("%s",&ss);
		WashClothes wc;
		vector<WashClothes> Clothes;
		for(int i = 0; i< m; ++i)
		{
			cin >> wc.time >> wc.color;
			//scanf("%d %s",&wc.time,&ss);
			//wc.color = ss;
			Clothes.push_back(wc);
		}
		sort(Clothes.begin(), Clothes.end(), cmp);
		vector<int> p;
		string color = Clothes[0].color;
		p.push_back(Clothes[0].time);
		int ret = 0;
		for(int i = 1; i< Clothes.size(); ++i)
		{
			if(Clothes[i].color != color)
			{
				ret += Bag(p);
				p.clear();
				p.push_back(Clothes[i].time);
				color = Clothes[i].color;
			}
			else p.push_back(Clothes[i].time);
		}
		ret += Bag(p);
		printf("%d\n",ret);
		//cout << ret << endl;
	}
	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