动态规划(2)
文章目录 动态规划(2) 1、聪明的寻宝人 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)
{ int dp[ n] ; for ( int i= 0 ; i< n; i++ ) dp[ i] = 1 ; for ( int i= n- 2 ; i>= 0 ; i-- ) { for ( int j= i+ 1 ; j< n; j++ ) { if ( arr[ i] >= arr[ j] ) dp[ i] = dp[ i] < ( dp[ j] + 1 ) ? ( dp[ j] + 1 ) : dp[ i] ; } } int max= 1 ; for ( int i= 0 ; i< n; i++ ) { if ( max< dp[ i] ) max= dp[ i] ; } printf ( "%d" , max) ;
}
4、找相似串
# include <iostream>
# include <cstring>
using namespace std;
const int MAX= 60 ;
void Similar ( )
{ char s[ MAX] ; int n, end; cin >> s>> n; int len_s = strlen ( s) ; char arr[ 20 ] [ MAX] ; int caozuo[ 20 ] ; int dp[ MAX] [ MAX] ; for ( int i = 0 ; i < n; i++ ) { cin>> arr[ i] ; } for ( int i = 0 ; i < len_s; i++ ) { dp[ 0 ] [ i] = i; } for ( int k = 0 ; k < n; 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++ ) { for ( int j = 1 ; j < len; j++ ) { if ( s[ i] == arr[ k] [ j] ) dp[ i] [ j] = dp[ i - 1 ] [ j - 1 ] ; else dp[ 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; }
}