17年春python班級作業>>>>20161201067

 1 #史上最醜的Python01背包 by 20161201067
 2 #問題描述：n組學生，分組進教室，教室容量為s，求最優解
 3 
 4 
 5 def booleans(seek,leng):
 6     result = []
 7     for i in range(0,leng):
 8         result.append(0)
 9         result[i] = int(seek)%2
10         seek /= 2
11     return result
12 
13 
14 def package(leng):
15     boolean01 = [[0]*leng]
16     blen = pow(2,leng)
17     for i in range(1, blen):
18         boolean01.append(booleans(i,leng))
19     return boolean01
20 
21 
22 def main():
23     print("請輸入學生組數：\n")
24     n = eval(input())
25     print("請輸入教室容量：\n")
26     s = eval(input())
27     m = []
28     sps = []
29     boolean01 = package(n)
30     for i in range(0,n):
31         print("請輸入第", i, "組學生的人數")
32         m.append(input())
33     for i in range(0,pow(2,n)):
34         stmp = 0
35         for j in range(0,n):
36             stmp += int(m[j]) if boolean01[i][j] else 0
37         sps.append(s - stmp)
38     sps.sort()
39     for i in range(0, pow(2,n)):
40         flag = 1
41         if sps[i] >= 0:
42             flag = 0
43             print("教室剩餘最大容量為：",sps[i])
44             break
45         if(flag):
46             print("問題無解")
47             break
48 
49 
50 main()

下圖為測試結果：