动态规划——背包问题笔记

# -*- coding: utf-8 -*-
# n为物品数量
# c为背包重量
# w为每个物品重量
# v为每个物品价值
def bag(n, c, w, v):  
	res=[[-1 for j in range(c+1)] for i in range(n+1)]
	for j in range(c+1):
		res[0][j] = 0
	for i in range(1, n+1):
		for j in range(1, c+1):
			res[i][j] = res[i-1][j]
			if j >= w[i-1] and res[i][j] < res[i-1][j-w[i-1]] + v[i-1]:
				res[i][j] = res[i-1][j-w[i-1]] + v[i-1]
	return res


def show(n, c, w, res):
	print('最大价值为:',res[n][c])
	x = [False for i in range(n)]
	j = c
	for i in range(1,n+1):
		if res[i][j] > res[i-1][j]:
			x[i-1] = True
			j -= w[i-1]
	print('选择的物品为:')
	for i in range(n):
		if x[i]:
			print('第',i,'个,',end='')
	print('')

if __name__ == '__main__':
	n = 4
	c = 10
	w = [5,2,8,3]
	v = [7,3,10,4]
	res = bag(n,c,w,v)
	show(n,c,w,res)