shell排序

starwing83

LZ的需求，我的代码改四个字节就能做到，可是何必呢= =贪心复杂度会更好的：

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

复制代码

python  "noname\2010-09-29-2.py"
0.48 a:0.13 b:0.23 c:0.05 e:0.07
0.46 r:0.13 q:0.20 r:0.13
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.33 g:0.21 r:0.03 s:0.04 t:0.05
Hit any key to close this window...

ashlv

回复 90# starwing83


    Orz,惯性思维,一看到就自然而然的套上去了

expert1

回复 80# starwing83


    按照你这个理解的话，用脚本我还真写不出来呢。

比如一堆数，有个0.49的，但是最小的大于0.1了，那么最优的也就是0.49这个了。
脚本写还真的得考虑一下啊

mr_caoke

回复 28# blackold


    他要求最大化，所以恐怕要先排序

ashlv

回复 93# expert1


    0.49可不是最优哇,题目没有要求尽可能大,只要求了小于0.5而已,所以取哪个都一样

expert1

回复 95# ashlv


    呵呵，我的意思是：找出满足小于0.5的最小K项，楼上的几个Python大概也是这个意思。
楼主的意思是：是找出满足小于0.5的最大K项

其实2个类似，shell找出最小的K
那么也是排序，满足0。5的前提下，把最大相加。

好看的附件

感觉排序的思路不错

starwing83

回复 95# ashlv


    他说的可是“按照我（starwing83）的理解”

expert1

回复 98# starwing83


    正解，哈哈

starwing83

回复 96# expert1


    额……………………我不是这个意思，我的代码和K无关，只是让和尽量接近0.5，至于取多少项我是不关心的= =