动态规划DB
动态规划DB
1.背包9讲
1.1 0-1背包
问题描述:有N个物品，每个物品重w~i~，价值Vi。有一个背包，容量为V，求价值最大时，装入的容量最多？
==要求==：每个物品只能拿一次
算法分析：
- 定义状态和选择：状态，背包的容量和可以选择的物品；选择，就是放入或不放入;
- dp[i] [v]数组的含义：dp[i] [v]的含义就是对于前i个物品，当前背包的容量为v，可获得的最大价值为dp[i] [v];
- 状态转移方程：
- 边界条件：dp=0；
代码框架
dp[状态1][状态2][…];
for(状态1:所有状态1的值)
{
for(状态2：所有状态2的值)
{
for(…){dp[状态1][状态2][…]}
}
}
影石Insta360公司福利 702人发布