POJ_3211_Washing Clothes
http://poj.org/problem?id=3211题意是求夫妇两人洗完衣服用的最小时间
先按衣颜色分类，对于每种颜色的衣服，最优解是都平分即V/2，背包容量为洗衣服的花费时间，用01背包来标记是否可以通过组合组成某个容量。最接近V/2的较大值就为两人洗完每种颜色衣服的最短时间，把各种颜色衣服的解加起来即为答案
我的代码【背包九讲的风格】：
#include <iostream>#include <iomanip>#include <fstream>#include <sstream>#include <algorithm>#include <string>#include <set>#include <utility>#include <queue>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <ctype.h>using namespace std;struct cloth{int w, index, sum; //sum表示这类衣服一个人洗的总时间char color; //index表示衣服数量，w储存每件衣服需要的时间}x;int dp;void _01pack (int cost, int weight, int sum){int j;for (j = sum; j >= cost; j--)dp = max (dp, dp+weight);}int main(){int m, n, i, j, temp, res;char str;while (cin >> m >> n){if (!m && !n)break;memset (x, 0, sizeof(x));for (i = 0; i < m; i++)cin >> x.color;for (i = 0; i < n; i++){cin >> temp >> str;for (j = 0; j < m; j++) //j表示衣服的种类if (strcmp (str, x.color) == 0) //颜色相同说明它属于j类衣服，于是加入到jx.sum += temp, x.w.index++] = temp;}/*for (i = 0; i < m; i++) //打表调试{cout << x.index << ' ' << x.color << "---" << endl;for (j = 0; j < x.index; j++)cout << x.w << "+++++";cout << x.sum;cout << endl;}*/res = 0;for (i = 0; i < m; i++) //i表示衣服的种类{memset (dp, 0, sizeof(dp));for (j = 0; j < x.index; j++)_01pack (x.w, x.w, x.sum);res += x.sum - dp.sum/2]; //累加每种衣服至少需要的时间}cout << res << endl;}return 0;}
页:
[1]