海口网站制作公司,一个网站3个相似域名,深圳网站建设 案例,网站制作-杭州算法刷题记录 Day36
Date: 2024.04.02
lc 416. 分割等和子集
//2. 一维数组
class Solution {
public:bool canPartition(vectorint nums) {// 将问题转化为从数组中任意取数#xff0c;使得容量为数组总和一半的背包内的价值尽可能大。// dp[j]表示容积为j的…算法刷题记录 Day36
Date: 2024.04.02
lc 416. 分割等和子集
//2. 一维数组
class Solution {
public:bool canPartition(vectorint nums) {// 将问题转化为从数组中任意取数使得容量为数组总和一半的背包内的价值尽可能大。// dp[j]表示容积为j的背包中能装的最大价值。// dp[j] for(int in-1; i0; i) max(dp[j], dp[j-nums[i]]nums[i]);int n nums.size();int count 0;for(auto x: nums){count x;}int half_count count / 2;vectorint dp(half_count1, 0);for(int i0; in; i){for(int jhalf_count; jnums[i]; j--){dp[j] max(dp[j], dp[j-nums[i]]nums[i]);}}if(dp[half_count] (count - half_count))return true;elsereturn false;}
};// 1. 二维数组
class Solution {
public:bool canPartition(vectorint nums) {// 将问题转化为从数组中任意取数使得容量为数组总和一半的背包内的价值尽可能大。// dp[i][j] 表示从第[0, i]个数中容积为j的背包的最大价值// dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]]v[i]);// 初始化第一行中j大于等于nums[0]的为j其余为0int n nums.size();int count 0;for(auto x: nums){count x;}int half_count count / 2;vectorvectorint dp(n, vectorint(half_count1, 0));for(int jnums[0]; jhalf_count; j){dp[0][j] nums[0];}for(int i1; in; i){for(int j0; jhalf_count; j){if(j nums[i])dp[i][j] dp[i-1][j];else{dp[i][j] max(dp[i-1][j], dp[i-1][j-nums[i]]nums[i]);}}}// for(int i0; in; i){// for(int j0; jhalf_count; j){// couti:i, j:j, value:dp[i][j]endl;// }// }if(dp[n-1][half_count] (count - half_count))return true;elsereturn false;}
};
