本文共 964 字,大约阅读时间需要 3 分钟。
链接:
题目大意:
Dearboy和他的女朋友一起洗m件衣服,共有n总颜色(每件衣服只有一种颜色)。 为了放置不同颜色互染,每次只能洗一种颜色的衣服,在这件衣服洗完之前不能洗另外一种衣服。 Dearboy和他女朋友可以同时一起洗衣服,但是不能同时洗同一件衣服,也不能同时洗不同种颜色的衣服。
一只每件衣服所需时间,问最少花费多少时间可以全部洗完。
分析:
首先可以很直观的判定,一定是把一种颜色的所有衣服都洗完再接着洗另外一种颜色的衣服,洗每种颜色所有衣服的总时间是分开独立的。
关键是洗同一种颜色的衣服时,Dearboy和他的女朋友怎样分配任务才可以最快完成? 最理想的情况时,两人各洗一半的时间。 所以,我们要尽量分配给两人的任务时长接近总时长的一半,最后洗完单种颜色的衣服所花的时间,取决于时长较大的那个。
很明显的可以用01背包来做,每件衣服的时间是容量也是价值,总时间的一半为背包的容量,然后01背包。
代码:
#include#include #include #include #include #include
转载地址:http://mpzni.baihongyu.com/