打卡第二天：
1. 动态规划开了一个头
中等：
376. 摆动序列 - 力扣（LeetCode）
这里又想到一个dp,再加一个符号判断，但是对于怎么找到对应符号的dp产生了困难。
发现答案解法中维护up 和 down 两个数组的思考很棒，如果nums[i] > nums[i-1] 则up[i] = up[i-1] +1 down[i] = down[i-1],最终比较up[n-1] 和 down[n-1]
53. 最大子数组和 - 力扣（LeetCode）
利用贪心和动规：本质上的思考是一样的。
当前面的连续和已经为负数后，对后面的最大子数组和并没有影响，应该另起炉灶
对于子序列，动态规划去遍历寻早前面符合的元素的思想
1035. Uncrossed Lines - 力扣（LeetCode）
392. 判断子序列 - 力扣（LeetCode）
这道题的进阶没有搞懂
2. 01背包问题
dfs解法：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300;
int n,capacity;
int weight[maxn];
int value[maxn];
int res=0;
void dfs(int index,int nowWeight,int nowValue){
if(index>=n) return;
dfs(index+1,nowWeight,nowValue);
if(nowWeight+weight[index]<=capacity){
if(nowValue+value[index]>res) res=nowValue+value[index];
dfs(index+1,nowWeight+weight[index],nowValue+value[index]);
}
}
int main() {
cin>>n>>capacity;
for(int i=0;i<n;i++)
{
cin>>weight[i]>>value[i];
}
dfs(0,0,0);
cout<<res<<endl;
return 0;
}
/*
输入
3 4
1 10
3 25
4 30
*/
//输出： 35
二进制枚举法：
//背包问题的暴力解法
#include <bits/stdc++.h>
using namespace std;
const int num_proj=5;
//按照需要输入宝物数量
int value[num_proj]={60,100,120,30,40};
int weight[num_proj]={10,20,30,10,20};
int bagage = 50;
//宝物的定义
int solution[num_proj];//中间方案
int final_solu[num_proj];//最终解决方案
int max_value=0;//最大价值
//这里讲暴力枚举，怎么枚举？每个物品都能放入或者不放入这说起来简单怎么实现呢
//这里是位运算的妙用，每个物品两个状态对应到二进制的零一
//全不放00000--》全放11111 （1<<num_proj
void get_bin_num(int num){
memset(solution,0,num_proj);
int i = num_proj;
while(num){ //这里得到的数组要注意我需要的顺序，是从前往后还是从后往前呢 30 11110 第一步30%2=0 选择num【4】=0
i--;
solution[i]=num % 2;
num = ceil(num /2);
}
}
//简单的十进制转二进制的函数，
//利用二进制来决定哪一个装，哪一个不装
/*
例如 31:
二进制为 1 1 1 1 1
这个就说明是所有物品1，2，3，4，5都装进去
*/
int main(){
int loop_num = 1<<num_proj;
//获得全部的数字，得到2^num_proj
while(loop_num>=0){
//遍历所有可能情况
loop_num--;
get_bin_num(loop_num);
int cur_weight = 0;
int cur_value = 0;
for(int i =0;i<5;i++){
if (solution[i]==1){
cur_weight += weight[i];
cur_value += value[i];
}
}
if(cur_value > max_value && cur_weight <= bagage){
/*cout<<cur_value<<" "<<cur_weight<<" "<<max_value<<endl;
比较获得最大值，如果满足条件:
1最大值比当前最大值大;
2当前重量小于等于背包承重;
则记录下解决办法，更新最大值。
*/
for(int j = 0;j<num_proj;j++){
final_solu[j] = solution[j];
}
max_value = cur_value;
}
}
cout<<"solution is : "<<endl;
for(int j = 0;j<num_proj;j++){
cout << final_solu[j]<<" ";
}
cout<<"最大的价值:"<<max_value<<endl;
}
//答案 0 1 1 0 0
二维的dp数组和一维的dp数组：为什么一维的时候要倒序？
AcWing 2. 01背包问题 为何优化为一维 为何逆序 - AcWing
3.总结
今天和汪总吃了烤肉，yeah。
明天也要学习~
