广州购物网站建设报价资源网站建设多少钱

当前位置： 首页 > news >正文

广州购物网站建设报价,资源网站建设多少钱,永久短网址生成,wordpress 主题课堂打卡第42天#xff0c;搞搞01背包。 今日任务 01背包问题#xff0c;你该了解这些#xff01;01背包问题#xff0c;你该了解这些#xff01; 滚动数组416.分割等和子集 背包问题1.0 #xff1a;0-1 背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weig… 打卡第42天搞搞01背包。 今日任务 01背包问题你该了解这些01背包问题你该了解这些 滚动数组416.分割等和子集 背包问题1.0 0-1 背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 暴力的解法应该是怎么样的呢 每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是o(2n)o(2^n)o(2n)这里的n表示物品数量。 所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化 01背包 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 viv_ivi​价值是 wiw_iwi​。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N 行每行两个整数 viv_ivi​,wiw_iwi​用空格隔开分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤1000 0viv_ivi​,wiw_iwi​≤1000 输入样例 4 5 1 2 2 4 3 4 4 5输出样例 8代码随想录 确定 dp 以及下标定义 dp[i][j] 表示从下标为 [0-i] 的物品里任意取放进容量为 j 的背包价值总和最大是多少。 确定递推公式 两个方向推出来dp[i][j] 不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以被背包内的价值依然和前面相同。) 放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值 所以递归公式 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。 状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。那么很明显当 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。 确定遍历顺序 二维数组的情况下 先遍历背包跟先遍历重量都可以 一维数组的情况下 先遍历重量 推导
#include bits/stdc.husing namespace std;int main() {int n, v;scanf(%d %d, n, v);vectorint weight(n);vectorint value(n);for(int i 0; i n; i) {scanf(%d, weight[i]);scanf(%d, value[i]);}// 初始化vectorvectorint dp(n, vectorint(v 1, 0));for(int i weight[0]; i v; i) {dp[0][i] value[0];}for(int i 1; i n; i) {for(int j 1; j v; j) {if(j weight[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j - weight[i]] value[i], dp[i - 1][j]);}}printf(%d, dp[n - 1][v]);return 0; }优化空间滚动数组 我们可以发现想知道dp[i][j] 需要知道dp[i - 1][j - weight[i]] 和 dp[i - 1][j]都只是前一层的信息所以我们可以用一个一维数组来保存信息只不过我们的遍历顺序第一次遍历的是物品第二层遍历的是背包而且是从大到小遍历因为想要知道大重量背包的最大价值总和要知道前面的小重量背包的最大价值总和而我们是用滚动数组保存如果从小到大遍历会改变小重量背包的最大价值总和。 #include bits/stdc.husing namespace std;int main() {int n, v;scanf(%d %d, n, v);vectorint weight(n);vectorint value(n);for(int i 0; i n; i) {scanf(%d, weight[i]);scanf(%d, value[i]);}// 初始化vectorint dp(v 1, 0);for(int i weight[0]; i v; i) {dp[i] value[0];}for(int i 1; i n; i) {for(int j v; j 1; j–) {if(j weight[i]) dp[j] dp[j];else dp[j] max(dp[j - weight[i]] value[i], dp[j]);}}printf(%d, dp[v]);return 0; }416. 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。提示 1 nums.length 2001 nums[i] 100 我的题解 回溯暴力搜索超时了哈哈哈 class Solution { public:bool backtracking(vectorint nums, int sum, int starIndex) {if(sum 0) return true;if(sum 0) return false;for(int i starIndex; i nums.size(); i) {sum - nums[i];if(backtracking(nums, sum, i 1)) return true;sum nums[i];}return false;}bool canPartition(vectorint nums) {int sum 0;for(int num : nums) sum num;if(sum % 2 1) return false;sort(nums.begin(), nums.end());return backtracking(nums, sum / 2, 0);} };01背包做法但是不是很理解。 class Solution { public:bool canPartition(vectorint nums) {int sum 0;for(int num : nums) sum num;if(sum % 2 1) return false;vectorint dp(sum / 2 1, 0);for(int i nums[0]; i sum / 2; i) dp[i] nums[0]; // 初始化for(int i 1; i nums.size(); i) {for(int j sum / 2; j 1; j–) {if(j nums[i]) dp[j] dp[j];else dp[j] max(dp[j - nums[i]] nums[i], dp[j]);}}return dp[sum / 2] sum / 2;} };代码随想录 class Solution { public:bool canPartition(vectorint nums) {int sum 0;// dp[i]中的i表示背包内总和// 题目中说每个数组中的元素不会超过 100数组的大小不会超过 200// 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了vectorint dp(10001, 0);for (int i 0; i nums.size(); i) {sum nums[i];}// 也可以使用库函数一步求和// int sum accumulate(nums.begin(), nums.end(), 0);if (sum % 2 1) return false;int target sum / 2;// 开始 01背包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]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] target) return true;return false;} };时间复杂度O(n^2)空间复杂度O(n)虽然dp数组大小为一个常数但是大常数