房山网站制作,招聘网站开发策划方案,潍坊网站建设报价费用,贵州网站建设设计动态规划#xff08;2#xff09; 文章目录 动态规划#xff08;2#xff09;1、聪明的寻宝人2、基因检测3、药剂稀释4、找相似串 1、聪明的寻宝人
#include iostream
using namespace std;
void MaxValue(int values[], int weights[], int n, int m) {int dp[21…动态规划2 文章目录 动态规划21、聪明的寻宝人2、基因检测3、药剂稀释4、找相似串 1、聪明的寻宝人
#include iostream
using namespace std;
void MaxValue(int values[], int weights[], int n, int m) {int dp[21][51] {0};for (int i 1; i n; i) {for (int j 1; j m; j) {if (weights[i - 1] j) {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]);} else {dp[i][j] dp[i - 1][j];}}}cout dp[n][m] endl;
2、基因检测
#include iostream
#include algorithm
#include cstring
#include string
using namespace std;void Similar(char *str1, char *str2) {int m strlen(str1);int n strlen(str2);int dp[51][51] {0};int maxLen 0;for (int i 1; i m; i) {for (int j 1; j n; j) {if (str1[i - 1] str2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;maxLen max(maxLen, dp[i][j]);} else {dp[i][j] 0; }}}cout maxLen ;
}3、药剂稀释
#include algorithm
using namespace std;void Cal(double arr[],int n)
{/********** Begin **********///补充代码完成任务int dp[n];for(int i0;in;i) dp[i]1;for(int in-2;i0;i--){for(int ji1;jn;j){if(arr[i]arr[j]) dp[i]dp[i](dp[j]1)?(dp[j]1):dp[i];}}int max1;for(int i0;in;i){if(maxdp[i]) maxdp[i];}printf(%d,max);/********** End **********/
}4、找相似串
#include iostream
#include cstring
using namespace std;
const int MAX60;
void Similar()
{/********** Begin **********/char s[MAX];int n,end;cin sn;//读取主串和子串个数int len_s strlen(s);char arr[20][MAX];int caozuo[20];//存操作次数int dp[MAX][MAX];//用数组dp[i][j]表示子串从1-i转换到主串的操作数。for (int i 0; i n; i)//读取子串{cinarr[i];} for (int i 0; i len_s; i){dp[0][i] i; //处理边界}for (int k 0; k n; k)//第k个子串{int len strlen(arr[k]);//子串长度//初始化for (int j 0; j len; j)dp[j][0] j;for (int i 1; i len_s; i)//i为主串下标{for (int j 1; j len; j)//j为子串下标{if (s[i] arr[k][j])dp[i][j] dp[i - 1][j - 1];elsedp[i][j] min(dp[i - 1][j], dp[i][j - 1]) 1;}}caozuo[k] dp[len_s-1][len-1];//存每个子串的最小操作数}end caozuo[0];for (int i 1; i n; i)end min(end, caozuo[i]); //找到最小操作数for (int i 0; i n; i){if (caozuo[i] end)cout arr[i] endl; //输出对应串}/********** End **********/
}
