动态规划（二）

大佬的第二个视频代码

视频链接

题目一：

题目描述：

在一个数组中（只包含正整数）找出一组不相邻的数，使得其和最大

解题思路：

关键思想： 每个数有选和不选两种选择。按前i个数的最优解来说，如果选这个数，则这个数的前一个数就不能选，因此此时的最优解就是前i-2个数的最优解加上当前的数字；如果不选这个数，则最优解就是前i-1个数的最优解。因此前i个数的最优解，就是这两个选择中的最优解（即最大值）。 起点： 当i=0时，最优解就是当前这个数；当i=1时，最优解就是前两个数中的最大值。

测试数据：

7 1 2 4 1 7 8 3

代码：

#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<cmath> using namespace std; int main(){ freopen("1.txt","r",stdin); int n; int arr[100],opt[100]; cin>>n; for(int i=0;i<n;i++){ cin>>arr[i]; } opt[0]=arr[0]; opt[1]=max(arr[0],arr[1]); for(int i=2;i<n;i++){ opt[i]=max(opt[i-2]+arr[i],opt[i-1]); } cout<<opt[n-1]<<endl; return 0; }

题目二：

题目描述：

给定一个数组arr（只包含正整数）和正整数s，从数组arr中任意选取几个数字，判断其和能否等于s

解题思路：

关键思想： 同样每个数有选和不选两种选择。在前i个数中，需要从中找到几个数使其的和为s，如果选择第i个数，则接下来考虑前i-1个数能否组成s-arr[i]；如果不选择第i个数，则考虑前i-1个数能否组成s。 特殊的点： 当s变成0时，返回true；当i等于0时，判断当前这个数是否正好等于s； 当当前的数大于s时，只判断不选择的情况。 dp: 将arr与s组成二维的bool类型的数组opt[][]，opt[i][s]代表的是前i个数能否组成和为s。首先要将第一行和第一列进行数据初始化。第一行代表i等于0的情况，此时只有当这个数（即arr[i]）正好等于s时才是true，其他都是false；第一列代表s等于0的情况，所以都是true。接下来依次计算每个位置的结果即可。最一般的情况：只要opt[i-1][j]（不选）和opt[i-1][j-arr[i]]（选）中有一个是true，则当前结果为true，否则为false。特殊情况：当前值大于s：只考虑不选的情况opt[i-1][j]。

测试数据：

6 9 3 34 4 12 5 2

代码（递归）：

#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<cmath> using namespace std; int n,s,arr[100]; bool opt[100][100]; bool rec_subset(int i,int rest){ if(rest==0) return true; else if(i==0) return rest==arr[i]; else{ return subset(i-1,rest)||subset(i-1,rest-arr[i]); } } int main(){ freopen("1.txt","r",stdin); memset(opt,0,sizeof(opt)); cin>>n>>s; for(int i=0;i<n;i++){ cin>>arr[i]; } cout<<rec_subset(n-1,s)<<endl; cout<<rec_subset(n-1,10)<<endl; cout<<rec_subset(n-1,11)<<endl; cout<<rec_subset(n-1,12)<<endl; cout<<rec_subset(n-1,13)<<endl; return 0; }

代码（dp）

#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<cmath> using namespace std; int n,s,arr[100]; bool opt[100][100]; bool dp_subset(int s){ //i==0的情况 for(int i=0;i<=s;i++) opt[0][i]=false; opt[0][arr[0]]=true; //s==0的情况 for(int i=0;i<n;i++) opt[i][0]=true; for(int i=1;i<n;i++){ for(int j=1;j<=s;j++){ if(arr[i]>j) opt[i][j]=opt[i-1][j]; else opt[i][j]=(opt[i-1][j-arr[i]]||opt[i-1][j]); } } return opt[n-1][s]; } int main(){ freopen("1.txt","r",stdin); memset(opt,0,sizeof(opt)); cin>>n>>s; for(int i=0;i<n;i++){ cin>>arr[i]; } cout<<dp_subset(s)<<endl; cout<<dp_subset(10)<<endl; cout<<dp_subset(11)<<endl; cout<<dp_subset(12)<<endl; cout<<dp_subset(13)<<endl; return 0; }