动态规划

2023-09-29 15:27| 来源: 网络整理| 查看: 265

动态规划——一维dp数组与二维dp数组

对于二维dp数组，递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

于其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。这就是一维dp数组

动态规划五部曲分析如下：确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。二维dp数组dp[i][j]，dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

确定dp数组的递推公式一维dp dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 二维dp dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); dp数组初始化

一维dp数组： dp[0]初始化为0，非零下标，如果“石头”价值存在负数，则初始化为负无穷，如果都是正数，则初始化为0 但其实还有一种情况，dp[0]初始化为1，就是当背包容量为0的时候，放0个物品，有部分题目是允许这种情况的二维dp数组： dp[i][0]初始化为0 dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最⼤价值初始化代码如下：

// 倒叙遍历 for (int j = bagWeight; j >= weight[0]; j--) { dp[0][j] = dp[0][j - weight[0]] + value[0]; // 初始化i为0时候的情况 } 数组遍历

一维数组遍历：

//注意：背包容量是从大到小遍历 for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }

二维数组遍历：

//物品重量和背包容量都是从小到大 // weight数组的大小就是物品个数 for(int i = 1; i < weight.size(); i++) { // 遍历物品 for(int j = 0; j

【本文地址】

公司简介

联系我们