shell排序

expert1

哦，看明白了，囧

expert1

回复 66# blackold


    print "";delete a;delete b
这个做咩用的？

blackold

回复 72# expert1


    呵呵，你也会白话？

   print ""就系换行。
   delete a 删除数组。

expert1

回复 73# blackold

我明白了

    呵呵，上学的时候同学都讲白话，略懂一些。

ashlv

貌似是背包问题

独行千行

没明白是什么

starwing83

75楼正解，楼上所有算法均错误（这题不能用贪心！）

给个Python代码（单纯做了选择）：

1. def pack(li, limit):
   
2.     limit = int(limit * 100)
   
3.     li = map(lambda x: int(x * 100), li)
   
4.     dp = [0] * (limit + 1)
   
5.     use = [[False] * len(li) for x in xrange(limit + 1)]
   
6.     for i in xrange(len(li)):
   
7.         for w in xrange(limit, li[i] - 1, -1):
   
8.             if dp[w] < dp[w - li[i]] + li[i]:
   
9.                 dp[w] = dp[w - li[i]] + li[i]
   
10.                 use[w] = use[w - li[i]][:]
    
11.                 use[w][i] = True
    
12.     li = map(lambda x: float(x) / 100, li)
    
13.     return float(dp[limit]) / 100, filter(None, map(lambda a, b: a and b, use[limit], li))
    
14. print pack([0.13, 0.23, 0.04, 0.45, 0.07], 0.49)
    
15. print pack([0.13, 0.23, 0.05, 0.45, 0.07], 0.49)
    
16. print pack([0.13, 0.20, 0.13, 0.33, 0.23], 0.49)
    
17. print pack([0.08, 0.11, 0.05, 0.45, 0.24], 0.49)

复制代码

注意：第一组数据贪心是过不了的！（答案是0.49，贪心的结果是0.47）

blackold

回复 78# starwing83


    我们理解错了？
对于这组数据：
a:0.13 b:0.23 c:0.05 d:0.45 e:0.07
p:0.13 q:0.20 r:0.13 s:0.33 t:0.23
h:0.08 g:0.11 r:0.05 y:0.45 s:0.24
g:0.01 q:0.02 r:0.03 s:0.04 t:0.05
g:0.21 q:0.22 r:0.03 s:0.04 t:0.05

按照你的理解，正确答案是什么？

starwing83

1. import re
   
2. 
   
3. def pack(li, limit):
   
4.     limit = int(limit * 100)
   
5.     li = map(lambda x: int(x * 100), li)
   
6.     dp = [0] * (limit + 1)
   
7.     use = [[False] * len(li) for x in xrange(limit + 1)]
   
8.     for i in xrange(len(li)):
   
9.         for w in xrange(limit, li[i] - 1, -1):
   
10.             if dp[w] < dp[w - li[i]] + li[i]:
    
11.                 dp[w] = dp[w - li[i]] + li[i]
    
12.                 use[w] = use[w - li[i]][:]
    
13.                 use[w][i] = True
    
14.     li = map(lambda x: float(x) / 100, li)
    
15.     return float(dp[limit]) / 100, filter(None, map(lambda a, b: a and b, use[limit], li))
    
16. 
    
17. def solve(s):
    
18.     for line in filter(None, s.split("\n")):
    
19.         table = {}
    
20.         li = []
    
21.         for item in line.split():
    
22.             k, v = re.match("(.*):(.*)", item).group(1, 2)
    
23.             table[float(v)] = item
    
24.             li.append(v)
    
25.         li = map(float, li)
    
26.         ans = pack(li, 0.49)
    
27.         print ans[0], " ".join(table[v] for v in ans[1])
    
28. 
    
29. #print pack([0.13, 0.23, 0.04, 0.45, 0.07], 0.49)
    
30. #print pack([0.13, 0.23, 0.05, 0.45, 0.07], 0.49)
    
31. #print pack([0.13, 0.20, 0.13, 0.33, 0.23], 0.49)
    
32. #print pack([0.08, 0.11, 0.05, 0.45, 0.24], 0.49)
    
33. solve("""
    
34. a:0.13 b:0.23 c:0.05 d:0.45 e:0.07
    
35. p:0.13 q:0.20 r:0.13 s:0.33 t:0.23
    
36. h:0.08 g:0.11 r:0.05 y:0.45 s:0.24
    
37. g:0.01 q:0.02 r:0.03 s:0.04 t:0.05
    
38. g:0.21 q:0.22 r:0.03 s:0.04 t:0.05
    
39. """)

复制代码

结果是：
0.48 a:0.13 b:0.23 c:0.05 e:0.07
0.49 r:0.13 r:0.13 t:0.23
0.48 h:0.08 g:0.11 r:0.05 s:0.24
0.15 g:0.01 q:0.02 r:0.03 s:0.04 t:0.05
0.48 g:0.21 q:0.22 t:0.05

我的理解是：从五个中选出几个值，使其相加的和小于但是尽可能接近0.5，这种选择是任意的，不带顺序的。因此排序可能会漏掉”一个很大的值加上一个很小的值刚刚好就是最优解“的情况（上次的回复，0.04 + 0.45就是最优解0.49，问题是你排序以后累加的时候，自动就pass了最大的0.45，因此得不到最优解。）