背包問(wèn)題：
對(duì)每種顏色的衣服求解背包問(wèn)題，和即為結(jié)果。
對(duì)于第i中顏色，所有時(shí)間和為sum，pack(i)返回洗該種衣服所花的最少時(shí)間。
最少時(shí)間問(wèn)題就是包容量為sum/2的01背包問(wèn)題，sum-dp[sum/2]就是結(jié)果
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int adj[105][105];
int dp[100005];
int pack(int i)
{
memset(dp,0,sizeof dp);
int sum=0,k,j;
for(k=1; k<=adj[i][0]; k++)
sum+=adj[i][k];
int v=sum/2;
for(k=1; k<=adj[i][0]; k++)
for(j=v; j>=adj[i][k]; j--)
{
if(dp[j]<dp[j-adj[i][k]]+adj[i][k])
dp[j]=dp[j-adj[i][k]]+adj[i][k];
}
return sum-dp[sum/2];
}
int main()
{
int m,n,j,i,value;
string str;
while(cin>>m>>n,n||m)
{
memset(adj,0,sizeof adj);
vector<string> vec;
for(i=1;i<=m; i++ )
{
cin>>str;
vec.push_back(str);
}
for(i=1; i<=n; i++)
{
cin>> value>>str;
for(j=0; j<vec.size(); j++)
{
if(str==vec[j])
{
adj[j][0]++;
adj[j][adj[j][0]]=value;
}
}
}
int ans=0;
for(i=0; i<vec.size(); i++)
ans+=pack(i);
cout<<ans<<endl;
}
system("pause");
return 0;
}