POJ 1141 Washing Clothes 背包问题


背包问题:
对每种颜色的衣服求解背包问题,和即为结果。

对于第i中颜色,所有时间和为sum,pack(i)返回洗该种衣服所花的最少时间。
最少时间问题就是包容量为sum/2的01背包问题,sum-dp[sum/2]就是结果
#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;
}

posted on 2010-08-13 17:00 田兵 阅读(323) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜