粉红色主题 模板 网站 在线预览,网页制作培训上海排名前十,wordpress流量统计代码,广西住房城乡建设厅代码随想录算法训练营第41天 [01背包的理论基础#xff0c;二维数组解法#xff0c;一维数组解法#xff0c;416. 分割等和子集] 一、01背包的二维数组解法 链接: 代码随想录. 思路#xff1a;dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能…代码随想录算法训练营第41天 [01背包的理论基础二维数组解法一维数组解法416. 分割等和子集] 一、01背包的二维数组解法 链接: 代码随想录. 思路dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值递推公式为 dp[i][j] max(dp[i-1][j],dp[i-1][j-weight[i]]value[i]) 做题状态看解析后做出来了 //二维dp数组实现
#include bits/stdc.h
using namespace std;int n, bagweight;// bagweight代表行李箱空间void solve() {vectorint weight(n, 0); // 存储每件物品所占空间vectorint value(n, 0); // 存储每件物品价值for(int i 0; i n; i) {cin weight[i];}for(int j 0; j n; j) {cin value[j];}// dp数组// dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值vectorvectorint dp(n,vectorint(bagweight1,0));for(int j 0 ;jbagweight;j){if(j weight[0]){dp[0][j] value[0];}}for(int i 1;in;i){for(int j 0;jbagweight;j){if(weight[i]j){dp[i][j] dp[i-1][j];}else{dp[i][j] max(dp[i-1][j],dp[i-1][j-weight[i]]value[i]);}}}cout dp[n-1][bagweight] endl;
}int main() {while(cin n bagweight) {solve();}return 0;
}
二、01背包的一维数组解法 链接: 代码随想录. 思路 一维数组实现 dp数组的含义 dp[j] 在背包大小为j时的最大价值 二维数组的递推公式为 dp[i][j] max(dp[i-1][j],dp[i-1][j-weight[i]value[i]) 一维数组的递推公式为 dp[j] max(dp[j],dp[j-weight[i]value[i]) 一维数组的解法里必须先遍历物品再遍历背包 并且遍历背包的时候必须时倒序 j代表空间空间必须比我选择的物品i的容量要大所以时jweight[i] 做题状态看解析后做出来了 //二维dp数组实现
#include bits/stdc.h
using namespace std;int n, bagweight;// bagweight代表行李箱空间void solve() {vectorint weight(n, 0); // 存储每件物品所占空间vectorint value(n, 0); // 存储每件物品价值for(int i 0; i n; i) {cin weight[i];}for(int j 0; j n; j) {cin value[j];}//一维数组实现 dp数组的含义 dp[j] 在背包大小为j时的最大价值//二维数组的递推公式为 dp[i][j] max(dp[i-1][j],dp[i-1][j-weight[i]value[i])//一维数组的递推公式为 dp[j] max(dp[j],dp[j-weight[i]value[i])vectorint dp(bagweight1,0);//一维数组的解法里必须先遍历物品再遍历背包//并且遍历背包的时候必须时倒序//j代表空间空间必须比我选择的物品i的容量要大所以时jweight[i]for(int i 0;in;i){for(int j bagweight;jweight[i];j--){dp[j] max(dp[j],dp[j-weight[i]]value[i]);}}cout dp[bagweight] endl;
}int main() {while(cin n bagweight) {solve();}return 0;
}
三、416. 分割等和子集 链接: 代码随想录. 思路把问题转化为01背包 相当于从nums里取数重量 价值 数值 有一个大小为target的背包能不能将背包装满 做题状态看解析后做出来了 class Solution {
public:bool canPartition(vectorint nums) {vectorint dp(10001, 0);int sum 0;for (int n : nums) {sum n;}if (sum % 2 1) {return false;}int target sum / 2;// 相当于从nums里取数重量 价值 数值// 有一个大小为target的背包能不能将背包装满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]);}}return dp[target] target;}
};
