poj3211 Washing Clothes(01 가방 문제)
Time Limit: 1000MS
Memory Limit: 131072K
Total Submissions: 6490
Accepted: 1828
Description
Dearboy was so busy recently that now he has piles of clothes to wash. Luckily, he has a beautiful and hard-working girlfriend to help him. The clothes are in varieties of colors but each piece of them can be seen as of only one color. In order to prevent the clothes from getting dyed in mixed colors, Dearboy and his girlfriend have to finish washing all clothes of one color before going on to those of another color.
From experience Dearboy knows how long each piece of clothes takes one person to wash. Each piece will be washed by either Dearboy or his girlfriend but not both of them. The couple can wash two pieces simultaneously. What is the shortest possible time they need to finish the job?
Input
The input contains several test cases. Each test case begins with a line of two positive integers M and N (M < 10, N < 100), which are the numbers of colors and of clothes. The next line contains M strings which are not longer than 10 characters and do not contain spaces, which the names of the colors. Then follow N lines describing the clothes. Each of these lines contains the time to wash some piece of the clothes (less than 1,000) and its color. Two zeroes follow the last test case.
Output
For each test case output on a separate line the time the couple needs for washing.
Sample Input
3 4
red blue yellow
2 red
3 blue
4 blue
6 red
0 0
Sample Output
10
Source
POJ Monthly--2007.04.01, dearboy
제목:http://poj.org/problem?id=3211
분석: 이 문제는 조금만 더 숨기면 01배낭 문제입니다. 배낭을 채워야 할 수도 있고 가장 많이 담아야 할 상황으로 바뀔 수도 있습니다. 즉, 01배낭으로 몇 개의 수를 판단하고 조합을 통해 이 수의 와/2에 최대한 접근할 수 있습니다.아주 좌절 했 다 = = 구체적으로 코드 를 보자!
코드:
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=111;
int g[mm][mm],t[mm],s[mm];
bool f[111111];
char color[mm][22],tmp[22];
int n,m;
int getid(char *s)
{
for(int i=0;i<m;++i)
if(strcmp(s,color[i])==0)return i;
return 0;
}
int main()
{
int i,j,k,ans;
while(scanf("%d%d",&m,&n),n+m)
{
for(i=0;i<m;++i)scanf("%s",color[i]),t[i]=s[i]=0;
for(i=0;i<n;++i)
{
scanf("%d%s",&k,tmp);
s[j=getid(tmp)]+=k;
g[j][t[j]++]=k;
}
for(ans=k=0;k<m;++k)
{
for(i=0;i<=s[k]/2;++i)f[i]=0;
f[0]=1;
for(i=0;i<t[k];++i)
for(j=s[k]/2-g[k][i];j>=0;--j)
if(f[j])f[j+g[k][i]]=1;
for(i=s[k]/2;i>=0;--i)
if(f[i])break;
ans+=s[k]-i;
}
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
less 명령으로 파일을 다시 씁니다.less 명령이란? 텍스트 파일을 한 화면에 표시하는 명령less /var/log/messages 에서 messages 로그 파일을 확인할 수 있습니다. 대체로 확인할 때 less 를 사용하는 것이 많을까 생각합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.