Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: