网站模板整站,湘潭网站建设磐石网络上班时间,网站的前台后台,多梦wordpress文档讲解#xff1a;背包问题二维 背包问题一维 分割等和子集 46.整数拆分
题目链接#xff1a;https://kamacoder.com/problempage.php?pid1046
思路#xff1a; 在一维dp数组中#xff0c;dp[j]表示#xff1a;容量为j的背包#xff0c;所背的物品价值可以最大为d… 文档讲解背包问题二维 背包问题一维 分割等和子集 46.整数拆分
题目链接https://kamacoder.com/problempage.php?pid1046
思路 在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。 dp[j]可以通过dp[j - weight[i]]推导出来dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。 dp[j - weight[i]] value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。也就是容量为j的背包放入物品i了之后的价值即dp[j] 此时dp[j]有两个选择一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]即不放物品i一个是取dp[j - weight[i]] value[i]即放物品i指定是取最大的毕竟是求最大价值。
核心代码
#include iostream
#include vector
using namespace std;
int main() {// 读取 M 和 Nint M, N;cin M N;vectorint costs(M);vectorint values(M);for (int i 0; i M; i) {cin costs[i];}for (int j 0; j M; j) {cin values[j];}vectorint dp(N 1, 0);for (int i 0; i M; i) {for (int j N; j costs[i]; --j) {dp[j] max(dp[j], dp[j - costs[i]] values[i]);}}cout dp[N] endl;return 0;
}
416.分割等和子集
题目链接https://leetcode.cn/problems/partition-equal-subset-sum/description/
思路 分析可知以下几点 1.背包的体积为sum / 2 2.背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值 3.背包如果正好装满说明找到了总和为 sum / 2 的子集。 4.背包中每一个元素是不可重复放入。 可知题目为01背包套模板即可。
核心代码
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;vectorint dp(10001, 0);for (int i 0; i nums.size(); i) {sum nums[i];}if (sum % 2 1) return false;int target sum / 2;for(int i 0; i nums.size(); i) {for(int j target; j nums[i]; j--) {dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}if (dp[target] target) return true;return false;}
};
今日总结 今日学习时长2h算是复习了背包问题。 参加了华为主管面感觉寄掉了寄寄寄。 接着冲击八股文。
