背包问题之poj3211
#include <iostream>#include <string.h>#include <vector>using namespace std;const int M=10;const int N=100;char color[M][N];vector<int>cost[M];int dp[100002];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++){cin>>color[i];cost[i].clear();}while (n--){char col[N];int time;cin>>time>>col;for (i=0;i<m;i++)if(strcmp(color[i],col)==0)break;if(i<m){cost[i].push_back(time);}}int ans=0;for (i=0;i<m;i++){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];}cout<<ans<<endl;}return 0;}
?
?
?
?
?
