做pc端网站服务,免费版企业邮箱注册,wordpress获取当前页面内容,wordpress自定义文章流程我家娃可太好看了#xff0c;有点担心月嫂走了没法照顾娃。
明天没有新的题#xff0c;所以我今天开个头吧。又懒了。 01背包问题 二维 思路看了一遍#xff0c;默写一下哈。甚至看了两遍#xff0c;但是还没开始搞。。。振作起来#xff01;#xff01;#xff01; 目…我家娃可太好看了有点担心月嫂走了没法照顾娃。
明天没有新的题所以我今天开个头吧。又懒了。 01背包问题 二维 思路看了一遍默写一下哈。甚至看了两遍但是还没开始搞。。。振作起来 目前看就是核心那一行有点问题具体看备注吧然后就是把验证代码也放上来了。 #include iostream
#include vector
using namespace ::std;
int main()
{int n;int bagweight;cin n;cin bagweight;// cout n是 n endl;// cout bagweight bagweight endl;vectorint weight(n, 0);vectorint value(n, 0);for (int i 0; i n; i){cin weight[i];}for (int i 0; i n; i){cin value[i];}// test// for (int i 0; i n; i)// {// cout weight是 weight[i] endl;// cout value是 value[i] endl;// }vectorvectorint dp(n, vectorint(bagweight 1, 0));for (int j weight[0]; j bagweight; j){dp[0][j] value[0];}for (int i 1; i n; i){for (int j 0; j bagweight; j){if (weight[i] j){//这行实际上也做了第0列第i行的赋值。dp[i][j] dp[i - 1][j];}else{//要考虑 j - weight[i] 是前一个价值可能性dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); }}}// for (int i 0; i n; i)// {// for (int j 0; j bagweight; j)// {// cout dp[i][j];// }// cout endl;// }cout dp[n-1][bagweight];return 0;
}随想录的写法学习一下。
//二维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(weight.size(), vectorint(bagweight 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j weight[0]已在上方被初始化为0// j weight[0]的值就初始化为value[0]for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];}for(int i 1; i weight.size(); i) { // 遍历科研物品for(int j 0; j bagweight; j) { // 遍历行李箱容量// 如果装不下这个物品,那么就继承dp[i - 1][j]的值if (j weight[i]) dp[i][j] dp[i - 1][j];// 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值// 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 该物品的价值构成else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}}cout dp[weight.size() - 1][bagweight] endl;
}int main() {while(cin n bagweight) {solve();}return 0;
} 01背包问题 一维 一维需要从后往前整浅试了一下然后发现背包要从0开始因为没有初始化i 0的情况 #include iostream
#include vector
using namespace ::std;
int main()
{int n;int bagweight;cin n;cin bagweight;// cout n是 n endl;// cout bagweight bagweight endl;vectorint weight(n, 0);vectorint value(n, 0);for (int i 0; i n; i){cin weight[i];}for (int i 0; i n; i){cin value[i];}// test// for (int i 0; i n; i)// {// cout weight是 weight[i] endl;// cout value是 value[i] endl;// }vectorint dp(bagweight 1,0);for (int i 0; i n; i){for (int j bagweight; j weight[i]; j--){dp[j] max(dp[j], dp[j - weight[i]] value[i]); }}//for (int j 0; j bagweight; j)//{// cout dp[i][j];//}//cout endl;cout dp[bagweight];return 0;
}416. 分割等和子集 力扣啦能少整点东西。他的思路是用背包重量和价值相同。 套路我自己其实还是有点想不到 背包的体积为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。 class Solution {
public:bool canPartition(vectorint nums) {int sum 0;for(int i 0;i nums.size();i){sum nums[i];}if(sum % 2 ! 0)return false;vectorintdp(sum/2 1,0);for(int i 0;i nums.size();i){for(int j sum/2;j nums[i];j--){dp[j] max(dp[j],dp[j - nums[i]] nums[i]);}}return (dp[sum/2] sum/2);}
}; 随想录和我做的差不多我就不贴上来了欠的债还了还有今天的没做加油
