首页 > 代码库 > POJ 3211 (分组01背包) Washing Clothes
POJ 3211 (分组01背包) Washing Clothes
题意：
小明有一个贤妻良母型的女朋友，他们两个一起洗衣服。
有M种颜色的N件衣服，要求洗完一种颜色的衣服才能洗另外一种颜色。
两人可以同时洗，一件衣服只能被一个人洗。
给出洗每件衣服所用的时间，求两个人洗完这些衣服所用的最短时间。
分析：
因为每种颜色是分开洗的，所以我们可以单独考虑一种颜色的衣服。
因为洗完这些衣服的总时间是固定的，所以两个人洗的时间尽可能的相等，这样洗完的时间最短。
所以将总时间的一半作为背包容量(这里总时间的奇偶性并不影响)，物品的体积和价值都是洗每件衣服所用的时间，然后进行01背包。
所求答案就是总时间减去背包的最大价值。
1 #include <iostream> 2 #include <map> 3 #include <cstdio> 4 #include <algorithm> 5 #include <vector> 6 #include <string> 7 #include <cstring> 8 using namespace std; 9 10 int dp[50000 + 50];11 12 int main()13 {14 freopen("in.txt", "r", stdin);15 int M, N;16 while(scanf("%d%d", &M, &N) == 2 && M && N)17 {18 map<string, vector<int> > cloth;19 string s;20 int l, ans = 0 ;21 vector<string> str;22 getchar();23 for(int i = 0; i < M; ++i)24 {25 cin >> s;26 str.push_back(s);27 }28 for(int i = 0; i < N; ++i)29 {30 cin >> l >> s;31 cloth[s].push_back(l);32 }33 for(int i = 0; i < M; ++i)34 {35 if(cloth[str[i]].empty()) continue;36 int n = cloth[str[i]].size();37 int sum = 0;38 for(int j = 0; j < n; ++j)39 sum += cloth[str[i]][j];40 41 memset(dp, 0, sizeof(dp));42 int V = sum / 2;43 for(int j = 0; j < n; ++j)44 for(int k = V; k >= cloth[str[i]][j]; --k)45 dp[k] = max(dp[k], dp[k-cloth[str[i]][j]] + cloth[str[i]][j]);46 47 48 ans += (sum - dp[V]);49 }50 51 printf("%d\n", ans);52 }53 54 return 0;55 }
POJ 3211 (分组01背包) Washing Clothes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。