太长不看：

• 求 排列数permutations时，必须外层for遍历背包容量。除此以外，一律外层for遍历物品
• 01背包问题（每个物品仅能被添加一次）使用滚动数组时，遍历背包容量时必须从大到小。而完全背包的物品每个物品可以添加无数次，所以遍历背包容量时必须从小到大

0-1 背包问题

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

背包最大重量为4。

物品为：

问背包能背的物品最大价值是多少？

S1 二维DP

使用二维数组，dp[i][j] 表示从下标为 [0-i]闭区间 的物品里任意取，放进容量为j的背包，价值总和最大是多少。

state transition equation:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

def test_01bag_problem(bag_size, weight, value) -> int:  
	dp = [[0 for _ in range(bag_size+1)] for _ in range(len(weight))] 
	
  # 遍历物品
	for i in range(len(weight)):  
		cur_weight, cur_val = weight[i], value[i] 
    # 遍历背包容量
		for j in range(1, bag_size+1):  
			if cur_weight > j: # 说明背包装不下当前物品.  
				dp[i][j] = dp[i - 1][j] # 所以不装当前物品.  
			else:  
				# 定义dp数组: dp[i][j] 前i个物品里，放进容量为j的背包，价值总和最大是多少。 
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight] + cur_val) 
	for row in dp:
	    print(row)
	return dp[-1][-1]

if __name__ == "__main__":  
	bag_size = 4 
	weight = [1, 3, 4] 
	value = [15, 20, 30] 
	assert(test_2_wei_bag_problem1(bag_size, weight, value) == 35)

S2  DP, use rolling array (滚动数组) to optimize space