网站建站图片,asp.net网站本机访问慢,wordpress cx udy,南宁高端网站题目:
你有一个背包和一些物品#xff0c;每个物品都有自己的体积和价值。背包有一个最大的体积限制。目标是选择一些物品放入背包#xff0c;使得背包中物品的总价值最大#xff0c;同时保证背包中物品的总体积不超过背包的体积限制。 思路: 初始化变量和数组#xff1a;…题目:
你有一个背包和一些物品每个物品都有自己的体积和价值。背包有一个最大的体积限制。目标是选择一些物品放入背包使得背包中物品的总价值最大同时保证背包中物品的总体积不超过背包的体积限制。 思路: 初始化变量和数组 w数组存储了各商品的体积重量。v数组存储了各商品的价值。bagV表示背包的最大容量。dp二维数组用于存储动态规划表的状态。dp[i][j]表示考虑前i件商品当背包容量为j时能够获得的最大价值。 动态规划过程 外层循环遍历所有商品i从1到4因为数组第一位留空。内层循环遍历所有可能的背包容量j从1到bagV。如果当前背包容量小于商品i的体积则不能装入该商品此时dp[i][j]的值与装入前一个商品时的值相同即dp[i - 1][j]。如果当前背包容量可以装下商品i则需要比较装入和不装入商品i的情况取两者的最大值作为dp[i][j]的值 不装入商品i最大价值为dp[i - 1][j]。装入商品i最大价值为商品i的价值加上剩余容量下的最大价值即v[i] dp[i - 1][j - w[i]]。 输出动态规划表 通过双层循环输出dp数组的所有值展示整个动态规划过程的状态变化。 代码: #includeiostream
using namespace std;
#include algorithmint main()
{// 商品的体积或重量数组第一位留空以便使数组下标与商品编号一致int w[5] { 0, 2, 3, 4, 5 };// 商品的价值数组第一位留空以便使数组下标与商品编号一致int v[5] { 0, 3, 4, 5, 6 };// 背包的最大容量int bagV 8;// 初始化动态规划表全部填充为0。dp[i][j]表示考虑前i个商品时背包容量为j时的最大价值int dp[5][9] { { 0 } };// 动态规划过程for (int i 1; i 4; i) { // 遍历所有商品i代表商品编号for (int j 1; j bagV; j) { // 遍历所有可能的背包容量j代表当前背包容量if (j w[i]) {// 如果当前背包容量装不下商品i则dp[i][j]的值与不包含商品i时相同// 即不选择当前商品i直接继承前一个商品的状态dp[i][j] dp[i - 1][j];} else {// 如果能装下商品i则比较不装入和装入商品i的情况取最大值// 不装入商品i直接继承前一个商品的状态即dp[i - 1][j]// 装入商品i当前商品的价值加上剩余容量下的最大价值即v[i] dp[i - 1][j - w[i]]dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]);}}}// 输出动态规划表for (int i 0; i 5; i) { // 遍历动态规划表的每一行for (int j 0; j 9; j) { // 遍历动态规划表的每一列cout dp[i][j] ; // 打印每个状态的值}cout endl; // 每行打印完毕后换行}return 0;
}
