Openjudge题目“最佳凑单”：生成列表的所有子列表

目录

36.（201711）最佳凑单

 笔记：如何生成列表的所有子列表

36.（201711）最佳凑单

描述

消费者为了享受商家发布的满减优惠，常常需要面临凑单问题。

假设有n件商品，每件的价格分别为p1,p2,...,pn，每件商品最多只能买1件。为了享受优惠，需要凑单价为t。那么我们要找到一种凑单方式，使得凑单价格不小于t（从而享受优惠），同时尽量接近t。被称为“最佳凑单”

如果不存在任何一种凑单方式，使得凑单价格不小于t（即无法享受优惠），那么最佳凑单不存在。

比如当前还差10元享受满减，可选的小件商品有5件，价格分别为3元、5元、8元、8元和9元，每件商品最多只能买1件。那么当前的最佳凑单就是11元（3元+8元）。

输入

第一行输入商品数n（n<=10）和需要凑单价t，如：
5 10
第二行输入每件商品的价格，如：
3 5 8 8 9

输出

如果可以凑单成功，则输出最佳凑单的价格，如：
输入
5 10
3 5 8 8 9
输出
11

如果无法凑单成功，则输出0。

如输入
5 10
1 1 1 1 1
则无法凑够10元，输出
0

样例输入

5 10
3 5 8 8 9

样例输出

11

提示

1. 为了简化问题，本题中每件商品最多只能买1件。
2. 不同的商品，即使价格相同也可以都买。比如5件商品，价格分别为3元、5元、8元、8元和9元。你可以买 8元(第3件)+8元(第4件)

来源

2017医学部计算概论-期末考试-蒋逸

n, t = list(map(int, input().split()))
p_li = list(map(int, input().split()))

notebook_0 = [[]]
if sum(p_li) < t:
    print(0)
else:
    notebook_1 = list()
    p_li.sort(reverse=True)
    for i in range(n):  # 生成p_li的所有子集
        for j in range(len(notebook_0)):
            notebook_0.append([p_li[i]]+notebook_0[j])
    for i in range(len(notebook_0)):  # 计算sum
        notebook_0[i] = sum(notebook_0[i])
    for i in range(len(notebook_0)):  # 选取所有能凑单的组合
        if notebook_0[i] >= t:
            notebook_1.append(notebook_0[i])
    print(min(notebook_1))

 笔记：如何生成列表的所有子列表

L = input().split()
List = [[]]
for i in range(len(L)):     # 定长
  for j in range(len(List)): # 变长
      List.append(List[j] + [L[i]])
 
print('List =', List)

输入：

1 2 3 4

输出：

List = [[], ['1'], ['2'], ['1', '2'], ['3'], ['1', '3'], ['2', '3'], ['1', '2', '3'], ['4'], ['1', '4'], ['2', '4'], ['1', '2', '4'], ['3', '4'], ['1', '3', '4'], ['2', '3', '4'], ['1', '2', '3', '4']] 

主要思路：

将L中的元素依次加入到List中，并与List原有的每一个元素进行组合 

参考：

如何基于python生成list的所有的子集 @https://www.jb51.net/article/174010.htm