import numpy as np
import math
import matplotlib.pyplot as plt
weight = [0, 1, 2, 4, 6]
value = [0, 1, 4, 6, 8]
V = 12
CoinNum = 4
#优化列表
optArray = np.zeros((CoinNum+1,V+1))
r = np.zeros((CoinNum+1,V+1))
#初始化
def initArr():
for i in range(V+1):
optArray[0][i] = math.inf
r[0][i] = 0
for j in range(CoinNum+1):
optArray[j][0] = 0
r[j][0] = 0
#迭代更新
def generateOpt():
for i in range(1,CoinNum+1,1):
for j in range(1,V+1,1):
optArray[i][j] = optArray[i - 1][j]
r[i][j] = r[i - 1][j]
if j - value[i] >= 0 and i-1>=0:
if optArray[i][j - value[i]] + weight[i] <= optArray[i - 1][j]:
optArray[i][j] = optArray[i][j - value[i]] + weight[i]
r[i][j] = i
#统计列表中元素个数
def single_list(arr, target):
return arr.count(target)
def findpath():
m=V
n=CoinNum
path=[]
numlist=[]
while r[n][m]!=0 and n>0 and m>0:
k = int(r[n][m])
path.append(k)
m = m - value[k]
for i in range(1,CoinNum+1,1):
numlist.append(single_list(path,i))
print(numlist)
print(path)
plt.bar(range(len(numlist)), numlist)
plt.show()
if __name__ == '__main__':
initArr()
generateOpt()
print(optArray)
print(r)
findpath()
