d*****8
发帖数: 38 | 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? |
C***U
发帖数: 2406 | 2 没看懂题目的意思
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?
|
d*****8
发帖数: 38 | 3 哪里不清楚？
我按我的理解用中文讲一下，
有很多装水的桶，
你可以把一个桶的水倒进另一个桶，（多余的水会溢出，浪费掉）
怎么倒，才能最后有最多装满水的桶？
设计一个算法，谢谢！ |
p*****2
发帖数: 21240 | 4
给个例子吧
【在 d*****8 的大作中提到】
: 哪里不清楚？
: 我按我的理解用中文讲一下，
: 有很多装水的桶，
: 你可以把一个桶的水倒进另一个桶，（多余的水会溢出，浪费掉）
: 怎么倒，才能最后有最多装满水的桶？
: 设计一个算法，谢谢！
|
l*********8
发帖数: 4642 | 5 我来猜着举个例子：
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 的大作中提到】
:
: 给个例子吧
|
C***U
发帖数: 2406 | 6 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 的大作中提到】
: 没有搜到以前类似的题。问一下大牛们：
: 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?
|
d*****8
发帖数: 38 | 7 谢谢，我应该早举例子的。因为没有题目，这是我自己设计的例子
假设所有桶的容积100，
最简单的例子：
桶里面装的水是：11， 80， 90
那么11倒入90的桶就可以得到1个满地桶。
稍复杂的例子
50， 70， 50， 31
用50+50, 70+31。最多2个桶
【在 p*****2 的大作中提到】
:
: 给个例子吧
|
d*****8
发帖数: 38 | 8 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， 那么只有一个桶满。
|
d*****8
发帖数: 38 | 9 这个稍微不同于最少硬币找零, 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
|
d*****8
发帖数: 38 | 10 这是我当时给的解法，请验证测试/优化，多谢!
由于可以溢出，greedy不适用所有情况。
我选择dynamic programming和greedy的结合。
首先排序，从水最多的开始（需要证明：由于没有要求给出所有可能解，所以最多开始
会减少步骤）
1.如果greedy可以找到正好满桶100的解，那么每次找最大的不溢出的桶；
这样可以最少的步骤找到部分解。
2.否则，依次找下一个水量少的桶，
这样会有多个不同的解，
我需要比较不同的方案，选择溢出/浪费水最少的一个
最少的能使总水量超过100的桶
比如：80, 78, 22, 11, 10.
80+11+10
78+22
max=2
我当时还想了更复杂的例子，想起来再贴
3.重复前两部，直到没有桶能装满。
多谢谢！ |
|
|
h**6
发帖数: 4160 | 11 是不是可以算算总水量，然后排序从小到大依次把桶装满。 |
y*******o
发帖数: 6632 | 12 sort
pour least bucket into most buckets.
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?
|
C***U
发帖数: 2406 | 13 能说下你的反例得意思吗？
这个稍微不同于最少硬币找零, 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个桶
|
C***U
发帖数: 2406 | 14 明白你的意思了。 但是我的解法刚好可以解决你的问题。 不是反例。
每个桶需要的水量数组是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 的大作中提到】
: 这个稍微不同于最少硬币找零, greedy算法，
: 1. 目标是最多的满桶;
: 2. 可以溢出桶
: 不满足greedy的条件：当前的最优解不受子问题影响.
: 像用在traveling salesman problem，
: 反例：
: 50， 70， 50， 31
: 用50+50, 70+31。最多2个桶
|
g***s
发帖数: 3811 | 15 目前都还没有正确解。
他的解法（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
|
C***U
发帖数: 2406 | 16 我说的算法对不对我不说。我的意思是他说的的不是我的算法得反例
目前都还没有正确解。他的解法（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
|
g***s
发帖数: 3811 | 17 你的算法反例更容易找。
【在 C***U 的大作中提到】
: 我说的算法对不对我不说。我的意思是他说的的不是我的算法得反例
:
: 目前都还没有正确解。他的解法（greedy DP)也不对，反例是4 4 4 9 9 9 88 88 88
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
|
C***U
发帖数: 2406 | 18 4 4 4 9 9 9 88 88 88
可以做反例
【在 g***s 的大作中提到】
: 你的算法反例更容易找。
|
w*********m
发帖数: 4740 | 19 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 的大作中提到】
: 没有搜到以前类似的题。问一下大牛们：
: 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?
|
w*********m
发帖数: 4740 | 20 so cannot split water in one bucket into more than one buckets?
【在 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， 那么只有一个桶满。
|
|
|
l********y
发帖数: 345 | 21 第一步应该先把总水量／容积＝最大可能满桶数算出来。 再从最多水桶开始，match少
水的桶，达到最大桶数时即可停止。 这样可以省一部分不必要的步骤。 |
R******1
发帖数: 58 | 22 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
|
d*****8
发帖数: 38 | 23 这个用贪婪法greedy就可以吧
88+9+4
3个桶
【在 g***s 的大作中提到】
: 目前都还没有正确解。
: 他的解法（greedy+DP)也不对，反例是4 4 4 9 9 9 88 88 88
|
d*****8
发帖数: 38 | 24 no
(多余的水会溢出，浪费掉)
【在 w*********m 的大作中提到】
: so cannot split water in one bucket into more than one buckets?
|
g***s
发帖数: 3811 | 25 你如何保证第一个出来的不是88+4+4+4
【在 d*****8 的大作中提到】
: 这个用贪婪法greedy就可以吧
: 88+9+4
: 3个桶
|
E*******0
发帖数: 465 | 26 换一个说法：
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. |
E*******0
发帖数: 465 | 27 I remember the 1st step is NP. |
g***s
发帖数: 3811 | 28 1 2在有范围正整数内非NP
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 E*******0 的大作中提到】
: I remember the 1st step is NP.
|
d*****8
发帖数: 38 | 29 88+4就不是greedy了
我之前说了先用greedy找正好的满桶，
每次找最大的不溢出的桶；
9是最大的不溢出的桶
4不是最大的，而88会溢出
1.如果greedy可以找到正好满桶100的解，那么每次找最大的不溢出的桶；
这样可以最少的步骤找到部分解。
【在 g***s 的大作中提到】
: 你如何保证第一个出来的不是88+4+4+4
|
d*****8
发帖数: 38 | 30 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***s
发帖数: 3811 | 31 "如果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*****8
发帖数: 38 | 32 用greedy解决正好100的问题，就是最大不溢出优先
这样可以节省时间。
88+9+4=101不满足正好100的条件，用第二种方法：
2.否则，依次找下一个水量少的桶，
这样会有多个不同的解，
我需要比较不同的方案，选择溢出/浪费水最少的一个 |
g***s
发帖数: 3811 | 33 给出你的具体算法吧。你这样太模糊，感觉就是所有情况都走一边，找最好的。那就不
是多项式时间内可解了。
【在 d*****8 的大作中提到】
: 用greedy解决正好100的问题，就是最大不溢出优先
: 这样可以节省时间。
: 88+9+4=101不满足正好100的条件，用第二种方法：
: 2.否则，依次找下一个水量少的桶，
: 这样会有多个不同的解，
: 我需要比较不同的方案，选择溢出/浪费水最少的一个
|
d*****8
发帖数: 38 | 34 溢出的情况，是要比较所有情况的
不是多项式时间 |
C***U
发帖数: 2406 | 35 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***s
发帖数: 3811 | 36 这里大家讨论的是 有范围正整数内是否有多项式解。
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***U
发帖数: 2406 | 37 谢谢 不好意思
【在 g***s 的大作中提到】
: 这里大家讨论的是 有范围正整数内是否有多项式解。
:
: we
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
v****c
发帖数: 29 | 38 他从subset sum做reduction
其实从3-partition problem reduce过来就可以了
即使整数是bounded，也是NPC
【在 g***s 的大作中提到】
: 这里大家讨论的是 有范围正整数内是否有多项式解。
:
: we
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
g***s
发帖数: 3811 | 39 说的是有范围正整数，指的是所有数字的和S是有范围，我们找算法是S的多项式级就可
以了。
Subset sum在这个条件下有DP解。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 v****c 的大作中提到】
: 他从subset sum做reduction
: 其实从3-partition problem reduce过来就可以了
: 即使整数是bounded，也是NPC
|
v****c
发帖数: 29 | 40 我的意思就是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***s
发帖数: 3811 | 41 哦，明白了。怪不得一直想不到解法。 :)
【在 v****c 的大作中提到】
: 我的意思就是subset sum有DP解
: 但是3-partition没有，所以可以从3-partition做reduction，而不从subset sum做
: 3-partition是strongly NPC，就算所有数字都有范围，也没polynomial算法
|
d*****8
发帖数: 38 | 42 多谢，那只有穷举比较了
当时忘了怎么证明
如果有刚好倒满的情况，可以先用greedy找到那些吗？
【在 v****c 的大作中提到】
: 我的意思就是subset sum有DP解
: 但是3-partition没有，所以可以从3-partition做reduction，而不从subset sum做
: 3-partition是strongly NPC，就算所有数字都有范围，也没polynomial算法
|
g***s
发帖数: 3811 | 43 关键是即使有刚好倒满的,你也不能保证就是最优解。你还是需要去搜索不满的情况。
看前面我给的例子。
不过，可以用贪心先求一组解，然后在此基础上做减枝可以稍微加速一点。
【在 d*****8 的大作中提到】
: 多谢，那只有穷举比较了
: 当时忘了怎么证明
: 如果有刚好倒满的情况，可以先用greedy找到那些吗？
|
