题意：
有2个人洗n件衣服，每件衣服有需要洗的时间和颜色，只能相同颜色的衣服两人一起洗，求洗完衣服的最少时间。
分析：
0-1背包判断某个重量是否能达到。
代码：
//poj 3211 //sep9 #include #include #include using namespace std; const int maxN=128; int m,n; map name; int v[maxN][maxN]; int dp[100028]; int pack(int k) { memset(dp,0,sizeof(dp)); dp[0]=1; int i,j,tot=0; for(i=1;i<=v[k][0];++i) tot+=v[k][i]; int ans=tot; for(i=1;i<=v[k][0];++i){ int w=v[k][i]; for(j=tot;j>=w;--j){ dp[j]=max(dp[j],dp[j-w]); if(dp[j]==1) ans=min(ans,max(j,tot-j)); } } return ans; } int main() { while(scanf("%d%d",&m,&n)==2){ if(m==0&&n==0) break; while(m--) scanf("%*s"); int num=0; name.clear(); for(int i=0;i >x>>a; if(name[a]==0){ name[a]=++num; v[name[a]][0]=0; } v[name[a]][++v[name[a]][0]]=x; } int ans=0; for(int i=1;i<=num;++i) ans+=pack(i); printf("%d\n",ans); } return 0; }