有一个背包可放入的物品总重量20公斤,共有m件物品,单个物品重量不超过15公斤。问:从这些物品中如何找出若干件,刚好是20公斤?(不考虑体积)
例如共有8个物品,分别为1,7,3,8,5,10,11,4公斤。算法思路如下:
把8件物品,看作8个位置,每个物品被选中记作1,不被选中记作0。显然,共有28=256种不同的选择方法。在这256种选择方法中,如果选中的物品重量之和等于20,就是我们要寻找的方案。
小李编写了python程序:由用户输入物品件数m,程序随机生成[1,15]之间的整数,表示每种物品的重量。请将程序划线⑴、⑵、⑶、⑷处填入适当的代码,将程序补充完整。
import random
def DToB(x,n):
if n<1: n=1
n=0
R=[0 for i in range(0,n)]
for i in range(n-1,-1,-1):
x=x//2
return R
m=int(input(“请输入物品件数 m”))
w=[for i in range(m)] #随机生成 m 件物品重量的列表
total=20
nm=
k=0
for x in range(0,nm): a=DToB(x,m)
T=[ ]
for i in range(0,m): if
a[i]==1:
if total==sum(T):
k=k+1
print(T)
print("共有",k,"种装入方法")