浮云家的花（1） - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>gardening - 拈花惹草

浮云家的花（1）

浮云家的花（1）# gardening - 拈花惹草

d*82015-05-14 07:05

1 楼

没有搜到以前类似的题。问一下大牛们：
Given a list of water buckets,
you can pour water from one to another buckets. if it's full, the remaining
water will be wasted.
how to get max number of full buckets?

l*d2015-05-14 07:05

2 楼

今年没时间秀，就挑几个特喜欢的
梦幻般的Anemone
peppermint 绣球，入了几棵，有复瓣的，还有两个endless summer，目前就这个开花
了。
传统玫瑰
漏斗菜，三年前种了4棵，就一棵依然存活，且越长越大！又入了一棵紫色和一棵蓝色
，希望能长成如此规模！
一望无际的sweet william

C*U2015-05-14 07:05

3 楼

没看懂题目的意思

remaining

【在 d*****8 的大作中提到】

: 没有搜到以前类似的题。问一下大牛们：
: Given a list of water buckets,
: you can pour water from one to another buckets. if it's full, the remaining
: water will be wasted.
: how to get max number of full buckets?

y*22015-05-14 07:05

4 楼

甜威廉依然那么壮观！这种颜色的漏斗花太漂亮了！浮云都在那入紫色和蓝色漏斗花？

【在 l*********d 的大作中提到】

: 今年没时间秀，就挑几个特喜欢的
: 梦幻般的Anemone
: peppermint 绣球，入了几棵，有复瓣的，还有两个endless summer，目前就这个开花
: 了。
: 传统玫瑰
: 漏斗菜，三年前种了4棵，就一棵依然存活，且越长越大！又入了一棵紫色和一棵蓝色
: ，希望能长成如此规模！
: 一望无际的sweet william

d*82015-05-14 07:05

5 楼

哪里不清楚？
我按我的理解用中文讲一下，
有很多装水的桶，
你可以把一个桶的水倒进另一个桶，（多余的水会溢出，浪费掉）
怎么倒，才能最后有最多装满水的桶？
设计一个算法，谢谢！

w*e2015-05-14 07:05

6 楼

我去年入的peppermint绣球，现在还是小小一颗呢，连花苞都看不到

【在 l*********d 的大作中提到】

p*22015-05-14 07:05

7 楼

给个例子吧

【在 d*****8 的大作中提到】

: 哪里不清楚？
: 我按我的理解用中文讲一下，
: 有很多装水的桶，
: 你可以把一个桶的水倒进另一个桶，（多余的水会溢出，浪费掉）
: 怎么倒，才能最后有最多装满水的桶？
: 设计一个算法，谢谢！

l*d2015-05-14 07:05

8 楼

就是漏死啊！

【在 y****2 的大作中提到】

: 甜威廉依然那么壮观！这种颜色的漏斗花太漂亮了！浮云都在那入紫色和蓝色漏斗花？

l*82015-05-14 07:05

9 楼

我来猜着举个例子：
5个桶：
桶1：容量：100，现有水量 80
桶2：容量：80，现有水量 70
桶3：容量：70，现有水量 10
桶4：容量：200，现有水量 25
桶5：容量：150，现有水量 35
则最好的方法是把桶4倒入1，桶5倒入桶2，这样桶1和2就满了。
如果把桶4和桶5都倒入桶3，那么只有一个桶满。

【在 p*****2 的大作中提到】

:
: 给个例子吧

l*d2015-05-14 07:05

10 楼

我从lowes 入的，都是挺大棵的了。

【在 w*******e 的大作中提到】

: 我去年入的peppermint绣球，现在还是小小一颗呢，连花苞都看不到

C*U2015-05-14 07:05

11 楼

Does greedy algorithm work?
Use an array A to record the water volume.
Use another array B to record water needed to fill buckets.
Use the first number in B to fill first number in A.
If it is full, done. Otherwise use the second to keep filling it.
A and B are sorted.

没有搜到以前类似的题。问一下大牛们：Given a list of water buckets,you can
pour water from one to another b........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

【在 d*****8 的大作中提到】

w*e2015-05-14 07:05

12 楼

今年入的吗？我是去年打折了入的几棵，今年长势似乎不咋样

【在 l*********d 的大作中提到】

: 我从lowes 入的，都是挺大棵的了。

d*82015-05-14 07:05

13 楼

谢谢，我应该早举例子的。因为没有题目，这是我自己设计的例子
假设所有桶的容积100，
最简单的例子：
桶里面装的水是：11， 80， 90
那么11倒入90的桶就可以得到1个满地桶。
稍复杂的例子
50， 70， 50， 31
用50+50, 70+31。最多2个桶

【在 p*****2 的大作中提到】

:
: 给个例子吧

l*d2015-05-14 07:05

14 楼

嗯哪！
可能受伤了，绣球都长得挺快的。
我前年入了一棵，已经挺大一片了。

【在 w*******e 的大作中提到】

: 今年入的吗？我是去年打折了入的几棵，今年长势似乎不咋样

d*82015-05-14 07:05

15 楼

longway2008这个例子很好，问题更复杂
我们先考虑简单的情况，比方说所有桶的容积是100
然后用简化问题的解法，按不同桶的容积改改

【在 l*********8 的大作中提到】

: 我来猜着举个例子：
: 5个桶：
: 桶1：容量：100，现有水量 80
: 桶2：容量：80，现有水量 70
: 桶3：容量：70，现有水量 10
: 桶4：容量：200，现有水量 25
: 桶5：容量：150，现有水量 35
: 则最好的方法是把桶4倒入1，桶5倒入桶2，这样桶1和2就满了。
: 如果把桶4和桶5都倒入桶3，那么只有一个桶满。

r*a2015-05-14 07:05

16 楼

今年雨多，有种冲动把整个花园都塞满绣球花

d*82015-05-14 07:05

17 楼

这个稍微不同于最少硬币找零, greedy算法，
1. 目标是最多的满桶;
2. 可以溢出桶
不满足greedy的条件：当前的最优解不受子问题影响.
像用在traveling salesman problem，
反例：
50， 70， 50， 31
用50+50, 70+31。最多2个桶

【在 C***U 的大作中提到】

: Does greedy algorithm work?
: Use an array A to record the water volume.
: Use another array B to record water needed to fill buckets.
: Use the first number in B to fill first number in A.
: If it is full, done. Otherwise use the second to keep filling it.
: A and B are sorted.
:
: 没有搜到以前类似的题。问一下大牛们：Given a list of water buckets,you can
: pour water from one to another b........
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

h*i2015-05-14 07:05

18 楼

感觉都是好高大上的花花呀～

d*82015-05-14 07:05

19 楼

这是我当时给的解法，请验证测试/优化，多谢!
由于可以溢出，greedy不适用所有情况。
我选择dynamic programming和greedy的结合。
首先排序，从水最多的开始（需要证明：由于没有要求给出所有可能解，所以最多开始
会减少步骤）
1.如果greedy可以找到正好满桶100的解，那么每次找最大的不溢出的桶；
这样可以最少的步骤找到部分解。
2.否则，依次找下一个水量少的桶，
这样会有多个不同的解，
我需要比较不同的方案，选择溢出/浪费水最少的一个
最少的能使总水量超过100的桶
比如：80, 78, 22, 11, 10.
80+11+10
78+22
max=2
我当时还想了更复杂的例子，想起来再贴
3.重复前两部，直到没有桶能装满。
多谢谢！

n*y2015-05-14 07:05

20 楼

我们家的anemone 也打骨朵了，有一根。

h*62015-05-14 07:05

21 楼

是不是可以算算总水量，然后排序从小到大依次把桶装满。

l*d2015-05-14 07:05

22 楼

柔柔娜，妹妹太喜欢绣球了。

【在 r****a 的大作中提到】

: 今年雨多，有种冲动把整个花园都塞满绣球花

y*o2015-05-14 07:05

23 楼

sort
pour least bucket into most buckets.

remaining

【在 d*****8 的大作中提到】

l*d2015-05-14 07:05

24 楼

哈哈，糖糖是如此感觉的？
你入微距了吗？

【在 h*******i 的大作中提到】

: 感觉都是好高大上的花花呀～

C*U2015-05-14 07:05

25 楼

能说下你的反例得意思吗？

这个稍微不同于最少硬币找零, greedy算法，1. 目标是最多的满桶;2. 可以溢出桶不
满足greedy的条件：当前的最优解不受子问题影响.像用在traveling sale........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

【在 d*****8 的大作中提到】

: 这个稍微不同于最少硬币找零, greedy算法，
: 1. 目标是最多的满桶;
: 2. 可以溢出桶
: 不满足greedy的条件：当前的最优解不受子问题影响.
: 像用在traveling salesman problem，
: 反例：
: 50， 70， 50， 31
: 用50+50, 70+31。最多2个桶

r*a2015-05-14 07:05

26 楼

掐指一算，已经5棵下地，还有三棵在路上。今年雨多啊，忍不住~~

【在 l*********d 的大作中提到】

: 柔柔娜，妹妹太喜欢绣球了。

C*U2015-05-14 07:05

27 楼

明白你的意思了。但是我的解法刚好可以解决你的问题。不是反例。
每个桶需要的水量数组是A： 30，50， 50，69
每个桶现有水量得数组B：31， 50， 50， 70
从31开始，把A里面第一桶满了。从A和B里面去掉，然后第二个桶去填充A里面剩下得
不是他自己得桶。

这个稍微不同于最少硬币找零, greedy算法，1. 目标是最多的满桶;2. 可以溢出桶不
满足greedy的条件：当前的最优解不受子问题影响.像用在traveling sale........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

【在 d*****8 的大作中提到】

l*d2015-05-14 07:05

28 楼

看样子大壮能帮忙挖坑了！

【在 r****a 的大作中提到】

: 掐指一算，已经5棵下地，还有三棵在路上。今年雨多啊，忍不住~~

g*s2015-05-14 07:05

29 楼

目前都还没有正确解。
他的解法（greedy+DP)也不对，反例是4 4 4 9 9 9 88 88 88

【在 C***U 的大作中提到】

: 明白你的意思了。但是我的解法刚好可以解决你的问题。不是反例。
: 每个桶需要的水量数组是A： 30，50， 50，69
: 每个桶现有水量得数组B：31， 50， 50， 70
: 从31开始，把A里面第一桶满了。从A和B里面去掉，然后第二个桶去填充A里面剩下得
: 不是他自己得桶。
:
: 这个稍微不同于最少硬币找零, greedy算法，1. 目标是最多的满桶;2. 可以溢出桶不
: 满足greedy的条件：当前的最优解不受子问题影响.像用在traveling sale........
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

l*d2015-05-14 07:05

30 楼

开了来秀秀！

【在 n****y 的大作中提到】

: 我们家的anemone 也打骨朵了，有一根。

C*U2015-05-14 07:05

31 楼

我说的算法对不对我不说。我的意思是他说的的不是我的算法得反例

目前都还没有正确解。他的解法（greedy DP)也不对，反例是4 4 4 9 9 9 88 88 88
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

【在 g***s 的大作中提到】

: 目前都还没有正确解。
: 他的解法（greedy+DP)也不对，反例是4 4 4 9 9 9 88 88 88

r*a2015-05-14 07:05

32 楼

现在一共5棵endless summer，分散在不同的shade情况下。再来5年就可以写论文了

【在 l*********d 的大作中提到】

: 看样子大壮能帮忙挖坑了！

g*s2015-05-14 07:05

33 楼

你的算法反例更容易找。

【在 C***U 的大作中提到】

: 我说的算法对不对我不说。我的意思是他说的的不是我的算法得反例
:
: 目前都还没有正确解。他的解法（greedy DP)也不对，反例是4 4 4 9 9 9 88 88 88
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

l*d2015-05-14 07:05

34 楼

我以前种的endless summer，就第一个夏天开了几朵，第二年就一朵，今年还没见到花
苞。我本来以为长大花就越多。
大壮V5！

【在 r****a 的大作中提到】

: 现在一共5棵endless summer，分散在不同的shade情况下。再来5年就可以写论文了

C*U2015-05-14 07:05

35 楼

4 4 4 9 9 9 88 88 88
可以做反例

【在 g***s 的大作中提到】

: 你的算法反例更容易找。

r*a2015-05-14 07:05

36 楼

已经知道提着水壶每天给浇水，可惜今年雨太多，实践的次数不多

【在 l*********d 的大作中提到】

: 我以前种的endless summer，就第一个夏天开了几朵，第二年就一朵，今年还没见到花
: 苞。我本来以为长大花就越多。
: 大壮V5！

w*m2015-05-14 07:05

37 楼

what's the initial state? any water in those buckets? full or not or any?
Any water added externally during the process?

remaining

【在 d*****8 的大作中提到】

l*d2015-05-14 07:05

38 楼

谁挖坑？

【在 r****a 的大作中提到】

: 已经知道提着水壶每天给浇水，可惜今年雨太多，实践的次数不多

w*m2015-05-14 07:05

39 楼

so cannot split water in one bucket into more than one buckets?

【在 l*********8 的大作中提到】

r*a2015-05-14 07:05

40 楼

大坑还是得自己挖。。。！！

【在 l*********d 的大作中提到】

: 谁挖坑？

l*y2015-05-14 07:05

41 楼

第一步应该先把总水量／容积＝最大可能满桶数算出来。再从最多水桶开始，match少
水的桶，达到最大桶数时即可停止。这样可以省一部分不必要的步骤。

m*a2015-05-14 07:05

42 楼

问一下，传统玫瑰是很香的品种吗？如果是，英文名字叫什么？我一直在寻找国内的那
种紫粉色的刺玫，总也找不到，主要是连中文名字我都不知道，无从下手。

R*12015-05-14 07:05

43 楼

I think this one will work as long as the capacity of each bucket is the
same. Of course, you can sort the buckets according to the required amount
of water if they have different capacities.
Note that if you pour one bucket, you can get at most one full bucket.

【在 y*******o 的大作中提到】

: sort
: pour least bucket into most buckets.
:
: remaining

l*d2015-05-14 07:05

44 楼

我鼻子不好，玫瑰的香气太淡了，没有很香的玫瑰。
国内的玫瑰不认识。

【在 m********a 的大作中提到】

: 问一下，传统玫瑰是很香的品种吗？如果是，英文名字叫什么？我一直在寻找国内的那
: 种紫粉色的刺玫，总也找不到，主要是连中文名字我都不知道，无从下手。

d*82015-05-14 07:05

45 楼

这个用贪婪法greedy就可以吧
88+9+4
3个桶

【在 g***s 的大作中提到】

: 目前都还没有正确解。
: 他的解法（greedy+DP)也不对，反例是4 4 4 9 9 9 88 88 88

T*m2015-05-14 07:05

46 楼

anemone漂亮，是练习摄影的好材料。

【在 l*********d 的大作中提到】

d*82015-05-14 07:05

47 楼

no
(多余的水会溢出，浪费掉)

【在 w*********m 的大作中提到】

: so cannot split water in one bucket into more than one buckets?

f*g2015-05-14 07:05

48 楼

这sweet william这么早就开了呀？
比我们这里早一个月至少

【在 l*********d 的大作中提到】

g*s2015-05-14 07:05

49 楼

你如何保证第一个出来的不是88+4+4+4

【在 d*****8 的大作中提到】

: 这个用贪婪法greedy就可以吧
: 88+9+4
: 3个桶

M*72015-05-14 07:05

50 楼

感觉没去年壮观啊。要打败龙大难度不小。

【在 l*********d 的大作中提到】

E*02015-05-14 07:05

51 楼

换一个说法：
1st step:
Given an integer array, and a value. Find a subset of the array such that
the sum equals the value.
2nd step:
Given an integer array, and a value. Find maximal groups of subset such that
the sum of each group equals the value.
3rd step:
Given an integer array, and a value. Find maximal groups of subset such that
the sum of each group equals to or bigger than the value.

l*d2015-05-14 07:05

52 楼

今年集中精力带娃，也要上班了。
娃最重要，其他都是浮云！
以后就看老乡的了！

【在 M****7 的大作中提到】

: 感觉没去年壮观啊。要打败龙大难度不小。

E*02015-05-14 07:05

53 楼

I remember the 1st step is NP.

M*72015-05-14 07:05

54 楼

老乡，你的国菊苗圃开张了没有？我想买几个品种。

g*s2015-05-14 07:05

55 楼

1 2在有范围正整数内非NP

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 E*******0 的大作中提到】

: I remember the 1st step is NP.

l*d2015-05-14 07:05

56 楼

感谢老乡支持，我今年努力把花分开，去年小南瓜小，都混在一起了。

【在 M****7 的大作中提到】

: 老乡，你的国菊苗圃开张了没有？我想买几个品种。

d*82015-05-14 07:05

57 楼

88+4就不是greedy了
我之前说了先用greedy找正好的满桶，
每次找最大的不溢出的桶；
9是最大的不溢出的桶
4不是最大的，而88会溢出
1.如果greedy可以找到正好满桶100的解，那么每次找最大的不溢出的桶；
这样可以最少的步骤找到部分解。

【在 g***s 的大作中提到】

: 你如何保证第一个出来的不是88+4+4+4

c*92015-05-14 07:05

58 楼

蓝色的anemone 太漂亮了！
换了装备，PP就是漂亮！！！

d*82015-05-14 07:05

59 楼

i guess 3rd is np, forget how to prove.
if it's just equal, it's easier

【在 E*******0 的大作中提到】

: I remember the 1st step is NP.

g*s2015-05-14 07:05

60 楼

"如果greedy可以找到正好满桶100的解，那么每次找最大的不溢出的桶；"
88+4+4+4=100
88+9+4=101
你到底greedy是先找正好１００优先，还是最大不溢出优先？
两者都有反例

【在 d*****8 的大作中提到】

: 88+4就不是greedy了
: 我之前说了先用greedy找正好的满桶，
: 每次找最大的不溢出的桶；
: 9是最大的不溢出的桶
: 4不是最大的，而88会溢出
: 1.如果greedy可以找到正好满桶100的解，那么每次找最大的不溢出的桶；
: 这样可以最少的步骤找到部分解。

d*82015-05-14 07:05

61 楼

用greedy解决正好100的问题，就是最大不溢出优先
这样可以节省时间。
88+9+4=101不满足正好100的条件，用第二种方法：
2.否则，依次找下一个水量少的桶，
这样会有多个不同的解，
我需要比较不同的方案，选择溢出/浪费水最少的一个

g*s2015-05-14 07:05

62 楼

给出你的具体算法吧。你这样太模糊，感觉就是所有情况都走一边，找最好的。那就不
是多项式时间内可解了。

【在 d*****8 的大作中提到】

: 用greedy解决正好100的问题，就是最大不溢出优先
: 这样可以节省时间。
: 88+9+4=101不满足正好100的条件，用第二种方法：
: 2.否则，依次找下一个水量少的桶，
: 这样会有多个不同的解，
: 我需要比较不同的方案，选择溢出/浪费水最少的一个

d*82015-05-14 07:05

63 楼

溢出的情况，是要比较所有情况的
不是多项式时间

C*U2015-05-14 07:05

64 楼

this problem should be an NP problem.
Reason:
Suppose bucket sizes = S/2, where S is sum of all water. question is can we
fill two buckets?
if 2 then answer to partition is yes
if 1 then no
So if we can solve this problem, then we can solve partition problem.

【在 d*****8 的大作中提到】

: 溢出的情况，是要比较所有情况的
: 不是多项式时间

g*s2015-05-14 07:05

65 楼

这里大家讨论的是有范围正整数内是否有多项式解。

we
★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 C***U 的大作中提到】

: this problem should be an NP problem.
: Reason:
: Suppose bucket sizes = S/2, where S is sum of all water. question is can we
: fill two buckets?
: if 2 then answer to partition is yes
: if 1 then no
: So if we can solve this problem, then we can solve partition problem.

C*U2015-05-14 07:05

66 楼

谢谢不好意思

【在 g***s 的大作中提到】

: 这里大家讨论的是有范围正整数内是否有多项式解。
:
: we
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

v*c2015-05-14 07:05

67 楼

他从subset sum做reduction
其实从3-partition problem reduce过来就可以了
即使整数是bounded，也是NPC

【在 g***s 的大作中提到】

: 这里大家讨论的是有范围正整数内是否有多项式解。
:
: we
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

g*s2015-05-14 07:05

68 楼

说的是有范围正整数，指的是所有数字的和S是有范围，我们找算法是S的多项式级就可
以了。
Subset sum在这个条件下有DP解。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 v****c 的大作中提到】

: 他从subset sum做reduction
: 其实从3-partition problem reduce过来就可以了
: 即使整数是bounded，也是NPC

v*c2015-05-14 07:05

69 楼

我的意思就是subset sum有DP解
但是3-partition没有，所以可以从3-partition做reduction，而不从subset sum做
3-partition是strongly NPC，就算所有数字都有范围，也没polynomial算法

【在 g***s 的大作中提到】

: 说的是有范围正整数，指的是所有数字的和S是有范围，我们找算法是S的多项式级就可
: 以了。
: Subset sum在这个条件下有DP解。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

g*s2015-05-14 07:05

70 楼

哦，明白了。怪不得一直想不到解法。 :)

【在 v****c 的大作中提到】

: 我的意思就是subset sum有DP解
: 但是3-partition没有，所以可以从3-partition做reduction，而不从subset sum做
: 3-partition是strongly NPC，就算所有数字都有范围，也没polynomial算法

d*82015-05-14 07:05

71 楼

多谢，那只有穷举比较了
当时忘了怎么证明
如果有刚好倒满的情况，可以先用greedy找到那些吗？

【在 v****c 的大作中提到】

g*s2015-05-14 07:05

72 楼

关键是即使有刚好倒满的,你也不能保证就是最优解。你还是需要去搜索不满的情况。
看前面我给的例子。
不过，可以用贪心先求一组解，然后在此基础上做减枝可以稍微加速一点。

【在 d*****8 的大作中提到】

: 多谢，那只有穷举比较了
: 当时忘了怎么证明
: 如果有刚好倒满的情况，可以先用greedy找到那些吗？