求一个简单的算法， 8 个数 int[] aaa = { 299, 649, 529, 519, 269, 649, 259, 219 }; 分成 2 组 4 个一组，大于等于 1400 就减 300
pyengwoei · 2015-11-10 14:45:24 +08:00 · 2296 次点击这是一个创建于 3303 天前的主题，其中的信息可能已经有所发展或是发生改变。
求一个简单的算法， 8 个数 int[] aaa = { 299, 649, 529, 519, 269, 649, 259, 219 }; 分成 2 组 4 个一组，大于等于 1400 就减 300 ，大于等于 1100 就减 200 ，大于等于 800 就减 100 。最后再减去每组当中最小的一个，求最后总和最小的组合方案
 |
1
a302800411 2015-11-10 14:49:26 +08:00
不是 homework 吧....
|
 |
2
pyengwoei OP 不是的，今天不是双 11 吗，我准备买 8 件衣服，就上面那些价格，算过去算过来，感觉最后应该可以省 400-500 老毛啦
|
 |
3
ljbha007 2015-11-10 14:56:08 +08:00
优惠力度这么大呀 求楼主公司网站 我也要买买买
|
|
4
pyengwoei OP 529, 519 ， 649 ， 649 这 4 个一组意思就是 这 4 件衣服 519 那件不算钱
|
|
5
a302800411 2015-11-10 15:35:51 +08:00
跑出来了....
519 269 259 219 一组 总共要 2144 |
 |
6
qiayue 2015-11-10 15:40:24 +08:00
能减一千多啊
|
 |
8
zealot0630 2015-11-10 17:36:19 +08:00  1
scala> def c(n: Int, l: List[Int]): Seq[(List[Int], List[Int])] = if (n == 0) Seq((Nil, l)) else if (n == l.size) Seq((l, Nil)) else c(n-1, l.tail).map{ case (s,n) => ((l.head :: s), n) } ++ c(n, l.tail).map{ case (s, n) => (s, (l.head :: n)) }
c: (n: Int, l: List[Int])Seq[(List[Int], List[Int])] scala> def coupon(l: List[Int]) = l.sum match { case x if x >= 1400 => x - 300; case x if x >= 1100 => x - 200; case x if x >= 800 => x - 100 } coupon: (l: List[Int])Int scala> c(4, List(299, 649, 529, 519, 269, 649, 259, 219)).minBy{ case (x,y) => coupon(x) - x.min + coupon(y) - y.min } res1: (List[Int], List[Int]) = (List(299, 269, 259, 219),List(649, 529, 519, 649)) |
 |
9
xuyinan503 2015-11-11 15:24:55 +08:00 via Android 1
299, 649, 529, 519, 269, 649, 259, 219
和为 3392 大于 2800 最优的情况可考虑两个 1400 以上 在考察实际数据，有两个 600+,两个 500+,四个 200+ 随意组合 600+,500+,两个 200+组成 1500+即可 最后花费 2792 |
|
10
xuyinan503 2015-11-11 15:26:19 +08:00 via Android
上边的不对，少看了一个条件
|
|
11
xuyinan503 2015-11-11 15:29:21 +08:00 via Android
zealot 应该是正解
|
|
12
pyengwoei OP @zealot0630 这个貌似可以啦
|
|
13
pyengwoei OP 不过 这个算法 是语言写的
|
|
14
pyengwoei OP @zealot0630 这个算法是什么语言写的啦 看不太明白
|
Select Language