网站建设属于什么科别,外贸在什么网站做,关于电商平台,电子网站怎么做的01 背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。
二维dp数组01背包
定义#xff1a;dp[i][j] 表示从下标为[0-i]的物品里任意取…01 背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
二维dp数组01背包
定义dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
递推公式
dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
初始化首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。 使用可以先遍历物品再遍历背包容量
// weight数组的大小 就是物品个数
for(int i 1; i weight.size(); i) { // 遍历物品for(int j 0; j bagweight; j) { // 遍历背包容量if (j weight[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}
}
一维dp数组滚动数组
把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[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
递推公式
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
初始化全赋值为0即可不会覆盖递推结果。
递推顺序逆序保证物品i只放入一次。
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]);}
}
416. 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1 输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 此题能够通回溯算法进行枚举子序列进行判断是否有子序列之和等于sum/2。 01背包问题题目中物品是nums[i]重量是nums[i]价值也是nums[i]背包体积是sum/2能否找到能装满背包的选取序列。如果nums[target]target集合中的子集总和正好可以凑成总和target。
bool canPartition(int* nums, int numsSize){//dp[i]中的i表示背包内总和int sum0;for(int i0;inumsSize;i){sumnums[i];}if(sum%21) return false;int targetsum/2;int dp[10002]{0};for(int i0;inumsSize;i){for(int jtarget;jnums[i];j--){dp[j]fmax(dp[j],dp[j-nums[i]]nums[i]);}}if(dp[target]target) return true;return false;
}
1049. 最后一块石头的重量 II 有一堆石头每块石头的重量都是正整数。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下 如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下就返回 0。 示例 输入[2,7,4,1,8,1]输出1 本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小。 dp[j]表示容量这里说容量更形象其实就是重量为j的背包最多可以背最大重量为dp[j]。 targetsum/2要求的是能够装满target的最大重量。
int lastStoneWeightII(int* stones, int stonesSize) {int sum0;for(int i0;istonesSize;i){sumstones[i];}int targetsum/2;int dp[15001]{0};for(int i0;istonesSize;i){for(int jtarget;jstones[i];--j){dp[j]fmax(dp[j],dp[j-stones[i]]stones[i]);}}return (sum-dp[target])-dp[target];
}
