动态规划

01背包 hdu2602http://acm.hdu.edu.cn/showproblem.php?pid=2602

每个物品一个。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define INF 0x3f3f3f3f
 7 using namespace std;
 8 int val[1010], vol[1010], dp[1010];
 9 int main()
10 {
11     int t, n, v;
12     cin >> t;
13     while(t--){
14         memset(dp, 0, sizeof(dp));
15         cin >> n >> v;
16         for(int i = 0; i < n; i++){
17             cin >> val[i];
18         }
19         for(int i = 0; i < n; i++){
20             cin >> vol[i];
21         }
22         for(int i = 0; i < n; i++){
23             for(int j = v; j >= vol[i]; j--){//从大到小
24                 dp[j] = max(dp[j], dp[j-vol[i]]+val[i]);
25             } 
26         }
27         cout << dp[v] << endl;
28     }
29     return 0;
30 }

完全背包 hdu2602改成完全背包的话

每个物品无数个

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define INF 0x3f3f3f3f
 7 using namespace std;
 8 int val[1010], vol[1010], dp[1010];
 9 int main()
10 {
11     int t, n, v;
12     cin >> t;
13     while(t--){
14         memset(dp, 0, sizeof(dp));
15         cin >> n >> v;
16         for(int i = 0; i < n; i++){
17             cin >> val[i];
18         }
19         for(int i = 0; i < n; i++){
20             cin >> vol[i];
21         }
22         for(int i = 0; i < n; i++){
23             for(int j = vol[i]; j <= v; j++){
24                 dp[j] = max(dp[j], dp[j-vol[i]]+val[i]);
25             } 
26         }
27         cout << dp[v] << endl;
28     }
29     return 0;
30 }

最长公共子序列LCS poj1458http://poj.org/problem?id=1458

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<vector>
 7 #define lson l, m, rt<<1
 8 #define rson m+1, r, rt<<1|1
 9 #define IO ios::sync_with_stdio(false);cin.tie(0);
10 #define INF 1e9
11 #define MAXN 1010
12 const int MOD=1e9+7;
13 typedef long long ll;
14 using namespace std;
15 char a[MAXN], b[MAXN];
16 int dp[MAXN][MAXN];
17 int main()
18 {
19     while(cin >> a+1 >> b+1){
20         memset(dp, 0, sizeof(dp));
21         int la = strlen(a+1), lb = strlen(b+1);
22         for(int i = 1; i <= la; i++){
23             for(int j = 1; j <= lb; j++){
24                 if(a[i] == b[j]){
25                     dp[i][j] = dp[i-1][j-1]+1;
26                 }
27                 else{
28                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
29                 }
30             }
31         } 
32         cout << dp[la][lb] << endl;
33     }
34     return 0;
35 }