代码随想录算法训练营day39|动态规划03
背包理论
二维背包dp的含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
根据dp数组的定义来初始化数组
如果写成一维数组，后遍历背包时，需要倒序，否则因为会借助前面的数据来更新数组，就会导致一个物品被多次放入
分割等和子集
要求集合里能否出现总和为sum/2的子集，所以背包大小为sum/2即可？
本题相当于物品的重量和价值都是nums[i],dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。那么找到dp[target]=target即可
原文地址：https://blog.csdn.net/Lindsey_feiren/article/details/143490804
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！