这是可行性的背包dp，就是问是否能够组成一个量
首先，洗完一种再洗一种，颜色之间是不影响的。
二，一种颜色的衣服已经定了，要洗的总量已经定了，要让总时间最少，就是要让两人洗的最为接近。（注意这道题只有两个人）
转化为可行性的问题，能否组成一种方案，使得这种方案最接近总量的一半，总量一定，这一半最接近，那么那一半也是最接近的
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<map> #include<string> #include<iostream> using namespace std; int n,m; int a[12][105]; bool f[100050]; int work2(int *a) { int tot=0; for (int i=1;i<=a[0];i++) tot+=a[i]; int kk=tot>>1; memset(f,false,sizeof(f)); f[0]=true; for (int i=1;i<=a[0];i++) for (int j=kk;j>=a[i];j--) f[j]=f[j]||f[j-a[i]]; for (int i=kk;i>=0;i--) if (f[i]) return tot-i; } void work() { memset(a,0,sizeof(a)); map<string,int> mp; string s; int x,ans=0; for (int i=1;i<=m;i++) { cin>>s; mp[s]=i; } for (int i=1;i<=n;i++) { cin>>x>>s; int k=mp[s]; a[k][++a[k][0]]=x; } for (int k=1;k<=m;k++) ans+=work2(a[k]); cout<<ans<<endl; } int main() { while (cin>>m>>n) { if (n==0&&m==0) break; work(); } return 0; }
