shell排序

expert1

回复 100# starwing83


实际上一回事吧。？

starwing83

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

复制代码

这个是完全满足LZ要求的代码，虽然复杂度搓了点= =

expert1

回复 97# 好看的附件


    不排序，根本没好办法。

ashlv

回复 98# starwing83


    Orz,我被你们绕晕了..

starwing83

回复 103# expert1


    你楼上的就是不排序的版本。

starwing83

回复 104# ashlv


    是这样的，我们两个的理解是这样的：选择几项，使得和最接近0.5
而楼主的理解是这样的：选择尽可能多的项目，但和不能大于等于0.5
expect1则想试试看别的题目，比如说：
    - 选择尽可能多的项目（LZ的要求）
    - 选择尽可能少的项目（只是一个贪心即可）

现在他的问题是，选择尽可能少的项目，是不是和“选择几项，使得和最接近0.5”这和问题等价。

答案是不等价的。因为很有可能最少的几个项目并不是最优解。我们两个理解的问题版本是无法贪心的。必须动态规划。

expert1

回复 105# starwing83


我也晕了，理清一下

首先要找出一个最接近0.5的数据，比如0.49，然后找出最接近（0.5-0.49）=0.1的数据比如0.09，那么2者之和满足了条件小于0.5，而且此时K最小了。
其他以此类推吧。

这次没错吧，这样好难了。\(^o^)/~

starwing83

回复 107# expert1


    你这样仍然得不到最优解，因为有可能是中间几个不大不小的数字加起来是最优的。

expert1

回复 108# starwing83


    哦，是哦，是这样，哎，最优解怎么做？

starwing83

回复 109# expert1


    最开始的Python代码不就是最优解么