神经质的农场主

38042 · 发表于 2015-8-23 17:31:00

本帖最后由 meteorite 于 2015-8-23 18:11 编辑
农场主有300个篮子，每个篮子里面放300个苹果，每个苹果有着相同或不同的价值（不超过三百英磅的随机整数来代表），所以有300的300次方种方式从每一个篮子里拿出一个苹果，农场主想从每一个篮子里挑出一个，然后使他们的价值最小，聪明的推油们你们有什么办法呢？

重点是 [FLY]如果农场主想通过最简单的方法知道前300种最便宜的组合方法，聪明的推油们又有什么方法呢？[/FLY]

每次操作只能知道一个苹果的价值而且不能瞬时排序，每一次排序是一次操作

38042 · 发表于 2015-8-23 17:54:40

本帖最后由 meteorite 于 2015-8-23 18:01 编辑
好吧这是一道算法题原题如下
You're given k arrays, each array has k integers. There are kk ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them

【input】
There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.
【output】
For each test case, print the k smallest sums, in ascending order.
【example】
3
1 8 5
9 2 5
10 7 6
2
1 1
1 2
【example-output】
9 10 12
2 2

@天马行空

22568 · 发表于 2015-8-23 17:48:46

求澄清题意..
我从lz的表述理解的是"有300个篮分别有300个价值不超300的果,要从每个篮取一个使得总价值最小".
难道这不是每个都最小?还用想?

好吧要知道前300种的话..本质上好像并没有什么好办法..直觉没错的话....

22568 · 发表于 2015-8-23 18:22:01

本帖最后由天马行空于 2015-8-23 18:28 编辑
这东西..本质上就是穷举..总共n^n种方案穷举就是了..
========华丽丽的分割线========
不过这里略微的优化些个的话..
每个篮都可能重复,而每个篮只取一个,所以重复的不需要管,先用n^2把重的剔除了..(~~并注意到给的数据已经有序了..~~看错..无视此括号..)先用n^2logn排序..
要求的是最小的若干,所以自然是从小的开始穷举;如果某种算法保证取的结果大体上是有序的,那么够数了之后就可以不管了..
注意到价值是离散的有界的正数..所以可能会有一些别的方法..(然而并不保证效率..)
========华丽丽的分割线========
好吧..给我的话其实我会怎么干呢..其实应该酱紫..
(要求取n个求和,要求最小的k个和.(这里k=n.))(给数据非负,已未排序.)

0. 给每个篮排序.
1. 维持一个大小为k的有序列表,初始为空.
2. 对每个篮:
3. 对此时那个列表和这个篮这k+n个数据,对应的kn个数对求和后取出最小的k个,更新至维持的那个列表.
4. 输出这个列表

复制代码

上述算法第3行当然不是把kn个都求出来再排序再选k个了..乃懂的吧..

38042 · 发表于 2015-8-23 18:50:00

@天马姐姐一看就是大神这道题的大体思想一下子就被提出了，但还不完整哦，用优先排序的话，怎样才能使两个篮子里的苹果的前k个和最快求出呢？

meteorite 于 2015-08-23 19:01:30 补充以下内容:

提示一下S(n+1)=Sn-An+A(n+1) 你们感受一下
@天马行空

22568 · 发表于 2015-8-23 19:25:31

ls问的是

引用
两个有序数列分别有a,b个数,怎么得到两两之间ab个和最小那k个?

我反正认为两个循环的嵌套更新那个列表..并且和已经超出k个的范围时当然就直接跳下一轮..就已经够简单的了..

引用
S(n+1)=Sn-An+A(n+1)

不明真相.

37041 · 发表于 2015-8-24 08:10:57

本帖最后由 tlwangnc 于 2015-8-24 08:23 编辑

这个不是ACM的题目么，感觉又回到了大学时代....循环即可，关键应该是每个篮子取出最小值的最优方案。
LZ是不是这个意思？

[IQ风暴] 神经质的农场主