动态规划DB

1.背包9讲

1.1 0-1背包

问题描述:有N个物品，每个物品重w~i~，价值Vi。有一个背包，容量为V，求价值最大时，装入的容量最多？

==要求==：每个物品只能拿一次

算法分析：

1. 定义状态和选择：状态，背包的容量和可以选择的物品；选择，就是放入或不放入;
2. dp[i] [v]数组的含义：dp[i] [v]的含义就是对于前i个物品，当前背包的容量为v，可获得的最大价值为dp[i] [v];
3. 状态转移方程：$F[i,v]=max(F[i-1,v],F[i-1,v-W_i]+V_i)F[i,v]=max(\{F[i-1,v],F[i-1,v-W\_i]+V\_i\})$
4. 边界条件：dp=0；

代码框架

dp[状态1][状态2][…];
for(状态1:所有状态1的值)
{
	for(状态2：所有状态2的值)
	{
		for(…){dp[状态1][状态2][…]}
	}
}