搜索引擎不友好的网站特征,龙冠专业网站建设,兴文县建设工程网站,wordpress 评论 设置✨博主#xff1a;命运之光 ✨专栏#xff1a;算法修炼之练气篇 ✨博主的其他文章#xff1a;点击进入博主的主页 前言#xff1a;学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了#xff0c;下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期… ✨博主命运之光 ✨专栏算法修炼之练气篇 ✨博主的其他文章点击进入博主的主页 前言学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期难度可谓是天差地别懂得都懂题目难度相比起练气期的题目难度提升很多所以要是各位蒟蒻小伙伴们看不懂筑基期的题目可以在练气期多积累积累练气期的题目也会不断更新大家一定要把基础打牢固了再来看筑基期的题目哈这样子也可以提高大家的学习效率一举两得加油(●◡●) 目录 ✨经典的01背包问题
小明的背包1
解题代码
dp数组打表如下
编辑 ✨经典01背包问题的解题思路
✨01背包的递推公式重要需要记忆
✨01背包的递推公式优化为一维数组重要需要记忆 ✨经典的01背包问题 让我们先看一道经典的01背包问题 小明的背包1 解题代码
#includebits/stdc.h
using namespace std;
int wi[105],vi[105],dp[1005][1005];
int main()
{int n,v;//n为行数v为背包的大小cinnv;//传入nv的值for(int i1;in;i){cinwi[i]vi[i];//传入重量和价值 }//写dp数组int i,j;for(i1;in;i){for(j1;jv;j){if(jwi[i]){dp[i][j]dp[i-1][j];//如果重量没j大的话就直接继承dp数组上一列的最优解直接dp[i-1][j]即可 }else{//若是比j大则进行比较这道题标准的01背包问题直接套用01背包推出的公式即可 dp[i][j]max(dp[i-1][j],dp[i-1][j-wi[i]]vi[i]); } }} coutdp[n][v];return 0;
}
dp数组打表如下 ✨经典01背包问题的解题思路
在C/C中可以使用动态规划来解决01背包问题。动态规划是一种常用的解决优化问题的算法思想它通过将问题分解为子问题并利用子问题的解来构建更大规模的问题的解。
以下是使用动态规划解决01背包问题的基本步骤 定义问题我们需要确定背包的容量和物品的重量和价值。假设背包的容量为C有n个物品每个物品的重量为w[i]价值为v[i]。 创建一个二维数组dp[n1][C1]其中dp[i][j]表示在前i个物品中背包容量为j时的最大价值。 初始化边界条件当物品数量为0或背包容量为0时最大价值都为0即dp[i][0] dp[0][j] 0。 递推关系对于每个物品i我们有两种选择放入背包或不放入背包。如果选择放入背包那么当前的最大价值为dp[i][j] dp[i-1][j-w[i]] v[i]如果选择不放入背包那么当前的最大价值为dp[i][j] dp[i-1][j]。我们选择两者中的较大值作为dp[i][j]的值。 递推计算使用循环遍历物品和背包容量根据递推关系计算dp[i][j]的值。 返回结果dp[n][C]即为问题的解表示在前n个物品中背包容量为C时的最大价值。
下面是一个示例代码演示了如何使用动态规划解决01背包问题
#include iostream
using namespace std;int knapsack(int C, int weights[], int values[], int n) {int dp[n 1][C 1];// 初始化边界条件for (int i 0; i n; i)dp[i][0] 0;for (int j 0; j C; j)dp[0][j] 0;// 计算最大价值for (int i 1; i n; i) {for (int j 1; j C; j) {if (weights[i - 1] j) {dp[i][j] max(values[i - 1] dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);} else {dp[i][j] dp[i - 1][j];}}}return dp[n][C];
}int main() {int C 10; // 背包容量int weights[] {2, 3, 4, 5}; // 物品重量int values[] {3, 4, 5, 6}; // 物品价值int n sizeof(weights) / sizeof(weights[0]); // 物品数量int max_value knapsack(C, weights, values, n);cout 最大价值 max_value endl;return 0;
}在这个示例中背包的容量C为10有4个物品重量分别为2、3、4和5价值分别为3、4、5和6。运行程序将输出最大价值为10即当背包容量为10时从这些物品中选择可以得到的最大价值。你可以根据实际情况修改输入的背包容量、物品重量和价值来解决不同的01背包问题。 ✨01背包的递推公式重要需要记忆
dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])其中dp[i][j]表示在前i个物品中背包容量为j时的最大价值w[i]表示第i个物品的重量v[i]表示第i个物品的价值。
递推公式的含义是在考虑第i个物品时我们有两种选择
不选择第i个物品即仅考虑前i-1个物品此时的最大价值为dp[i-1][j]。选择第i个物品那么背包的容量就会减少变为j-w[i]此时的最大价值为dp[i-1][j-w[i]] v[i]即在考虑前i-1个物品、背包容量为j-w[i]时的最大价值再加上第i个物品的价值v[i]。
我们选择上述两种选择中的较大值作为dp[i][j]的值即表示在考虑前i个物品、背包容量为j时的最大价值。
需要注意的是上述递推公式中的dp数组是一个二维数组大小为(n1) x (C1)其中n表示物品的数量C表示背包的容量。初始化时需要设置边界条件即dp[0][j] dp[i][0] 0表示当物品数量为0或背包容量为0时的最大价值为0。
✨01背包的递推公式优化为一维数组重要需要记忆
dp[j] max(dp[j], dp[j-w[i]] v[i])其中dp[j]表示背包容量为j时的最大价值w[i]表示第i个物品的重量v[i]表示第i个物品的价值。
