产品设计私单网站,厦门网站建设 金猪,基础网站建设公司,做的网站怎么转成网址链接学习资料#xff1a;代码随想录
这一块儿学得挺痛苦
注#xff1a;文中含大模型生成内容
动态规划#xff1a;01背包理论基础
卡码网第46题
思路#xff1a;五部曲
定义#xff1a;dp[i][j]为第i个物品背包容量为j#xff0c;能装下的最大价值
递推公式#xff1… 学习资料代码随想录
这一块儿学得挺痛苦
注文中含大模型生成内容
动态规划01背包理论基础
卡码网第46题
思路五部曲
定义dp[i][j]为第i个物品背包容量为j能装下的最大价值
递推公式dp[i][j]的值等于dp[i-1][j]的值和dp[i-1][j-weight[i]]value相比的最大值后者为看放下当前物品减去当前物品的容量能放下什么价值当然要是放不下当前物品就算了保持原来的值把
初始化左边dp[i][0]背包容量为0都初始化为0挺好的就是不用管了
dp[0][j],容量j能把物品0放上就放上放不上就是0
遍历顺序怎么着都行
打印略
#include bits/stdc.h
using namespace std;int main(){int materials,N;cinmaterialsN;vectorint space(materials,0);for(int i0;imaterials;i){cinspace[i];}vectorint value(materials,0);for(int i0;imaterials;i){cinvalue[i];}vectorvectorint dp(materials,vectorint(N1,0)); //dp[i][j]表示有i个材料可以放背包能装的空间为j时的最大价值,从行李空间为0开始递推for(int jspace[0];jN;j) dp[0][j] value[0];for(int i1;imaterials;i){ //i从1开始否则在递推函数处会索引负数for(int j0;jN;j){if(jspace[i]) dp[i][j] dp[i-1][j]; //防止下面出现负索引else{dp[i][j] max(dp[i-1][j],dp[i-1][j-space[i]]value[i]); //递推公式得画图模拟一下}}}cout dp[materials-1][N]endl; //第materials个物品下标为materials-1 } 动态规划01背包理论基础滚动数组
卡码网第46题 滚动数组是把原先的二维dp数组压缩成一维了就等于看新一个物品能不能装上的时候就按规矩累计之前的结果然后把之前的覆盖掉
主要在遍历方向上很难
一是j要倒着遍历
TA说得很清楚二维是根据上一个物品更新的。而一维数组是在本行根据本物品更新的。正序的化就会产生能多次放该物品的错觉实际上该物品只能放一次 为什么不能先遍历背包还是让TA帮我模拟一下不行啊先遍历背包的话只能加上一个物品。 啊这不就是我的贾维斯吗我能获得一份开发贾维斯的工作吗
我自己模拟了一下正向遍历j在外层不行会出现重复放一个物品的问题。总之根据递推公式来看还是要提取上一轮的信息不要让上一轮的信息被本轮信息覆盖 416. 分割等和子集
力扣题目链接
思路关键在于如何将其转换为背包问题
dp[j]为背包容量为j能装的最大价值那么在这里value[i]和weight[i]都是nums[i];背包容量是数字和的一半sum/2,是那个target如果背包容量target能装target就是能对半儿分了
// 五部曲
// dp定义dp[j] 容量为j的背包能装的价值为dp[j]
// 递推公式按背包来价值和重量都是这个数的值
// 初始化根据递推公式的max要选最大的nums都是正整数所以都初始化为最小的正整数0
// 遍历顺序按背包来
// 打印
class Solution {
public:bool canPartition(vectorint nums) {vectorint dp(100*200/21); //根据题意区间写的int sum 0;for(int num:nums){sumnum;} if (sum%2!0) return false; int target sum/2;for(int i0;inums.size();i){for(int jtarget;jnums[i];j--){dp[j] max(dp[j],dp[j-nums[i]]nums[i]);}}return dp[target] target;}
}; https://www.youtube.com/watch?vbI_GJHCePlY今日发现一件艺术品搁5、6年前我可能是他们的受众现在的我没有耐心连着看第三遍了。Anyway祝大家今晚睡个好觉明天是Sunday Morning哦
