超星 - 10. 动态规划 - 查题吧

填空题

补充下列程序（爬楼梯问题）：def goUpStairs(n):if n < 1:return 0if n == 1:return 1if n == 2:return 2a,b = 1,2sum = 0for i in :sum = a + breturn sumgoUpStairs(10)

填空题

补充下列程序（背包问题）：def backpack_record(goods, c, w, v):backpack_rec = [[0 for i in range(c+1)] for i in range(len(goods)+1)]for i in range(, len(goods)+1):for j in range(, c+1):if j < w[i - 1]:backpack_rec[i][j] = backpack_rec[i-1][j]else:backpack_rec[i][j] = max(backpack_rec[i-1][j],backpack_rec[i-1][j-w[i-1]] + v[i-1])return backpack_recdef backpack_results(goods, c, w, res):print('可容纳最大价值为:', res[len(goods)][c])x = [False for i in range(len(goods)+1)]j = ci = len(goods)while i>=0:if :x[i] =j -=i -= 1print('选择的物品为:')for i in range(len(goods)+1):if x[i]:print('第', i, '个,', end='')print('')goods = ['a', 'b', 'c', 'd']c = 8w = [2, 4, 5, 3]v = [5, 4, 6, 2]res = backpack_record(goods, c, w, v)backpack_results(goods, c, w, res)

1