本文共 1922 字，大约阅读时间需要 6 分钟。
这是我的代码，一直是wa
#include <iostream>
#include <cstring> #include <cstdio> #include <map> #include <string> #include <vector> #include <algorithm> #include <numeric> #include <cmath> using namespace std; int colors; int clothes; int dp[100002]; map<string,vector<int> > index; int main() { while (scanf("%d%d",&colors,&clothes)!=EOF) { if(colors==0 && clothes == 0) break; char line[150]= {0}; for (int i=0;i<colors;++i) { scanf("%s",line); } for (int i=0;i<clothes;++i) { int time; string coStr; cin>>time>>coStr; index[coStr].push_back(time); } map<string,vector<int> >::iterator iter; int all=0; for (iter = index.begin();iter!=index.end();++iter) { vector<int>& times = iter->second; int sum = accumulate(times.begin(),times.end(),0); //cout<<sum<<endl; int vol = sum/2; memset(dp,0,sizeof(dp)); for (int i=0;i<times.size();++i)//01背包问题 { for (int v=vol;v>=times[i];--v) { dp[v] = max(dp[v],dp[v-times[i]] +times[i]); } } all +=sum - dp[vol]; } cout<<all<<endl; } return 0;}
下面是网上的代码，却是ac，基本上差不多
#include<stdio.h>
#include<string.h> #include<vector> using namespace std; const int M = 10; const int N = 100; char color[M][N];//存储颜色,及其对应的id vector<int>cost[M];//存储每种颜色对应的衣物所需时间 int dp[10000+2]; inline int max(int a,int b) { return a>b?a:b; } int main() { int n,m; while(scanf("%d%d",&m,&n)!=EOF) { if(m==0&&n==0)break; int i,j; for(i=0;i<m;i++) { scanf("%s",color[i]);//将每一种颜色输入其中 cost[i].clear(); } while(n--) //输入每一件衣服的基本信息 { char col[N]; int time; scanf("%d%s",&time,col); for(i=0;i<m;i++) if(strcmp(col,color[i])==0)break; if(i<m) //将当前衣服信息放入对应的颜色内 { cost[i].push_back(time); } } int ans = 0; for(i=0;i<m;i++) //对每一种颜色的衣服进行01背包建模 { memset(dp,0,sizeof(dp)); int sz = cost[i].size(); int k,mid ,sum = 0; for(j=0;j<sz;j++)sum += cost[i][j]; mid = sum/2; for(j=0;j<sz;j++) { for(k = mid;k>=cost[i][j];k--) { dp[k] = max(dp[k],dp[k-cost[i][j]]+cost[i][j]); } } ans = ans + sum - dp[mid]; } printf("%d\n",ans); } return 0; }转载地址：http://qfeti.baihongyu.com/