1. 最大连续子数组和
求数组中连续的一个或多个子数组的最大和，并记录开始和结束位置
#include <iostream>
#include <fstream>
#define INF 0x7fffffff
#define max(x, y) x > y ? x : y
using namespace std;
int main()
{
ifstream cin("in.txt");
int n, buf[100], dp[100], start[100];
while(cin >> n)
{
for(int i = 1; i <= n; ++i)
{
cin >> buf[i];
dp[i] = buf[i]; //初始状态，以一个元素结尾的最大连续子数组和是其自身
start[i] = i; //初始状态，子数组的起点是自身下标
}
dp[0] = 0;
for(int i = 1; i <= n; ++i)
{
//dp[i] = max(dp[i], dp[i-1]+buf[i]);
if(dp[i] < dp[i-1]+buf[i])
{
dp[i] = dp[i-1]+buf[i];
start[i] = start[i-1];
}
}
int ans = -INF;
int end = 0;
for(int i = 1; i <= n; ++i)
{
if(ans < dp[i])
{
ans = dp[i];
end = i;
}
}
for(int i = start[end]; i <= end; ++i)
cout << buf[i] << " ";
cout << endl << ans << endl;
}
return 0;
}
1.1 最大子矩阵和
算法思想：假设最大子矩阵从i行到j行，将i行到j行的所有列相加，即转化为一维最大连续子数组和的问题
#include <stdio.h>
#include <string.h>
#define INF 0x7fffffff
#define max(x, y) x > y ? x : y
//最大连续子数组和
int sumOfArray(int a[], int n)
{
int max = -INF, sum = 0;
for(int i = 1; i <= n; ++i)
{
if(sum >= 0)
sum += a[i];
else
sum = a[i];
if(sum > max)
max = sum;
}
return max;
}
int main()
{
freopen("in.txt", "r", stdin);
int maze[100][100];
int m, n;
while(scanf("%d%d", &m, &n) != EOF)
{
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
scanf("%d", &maze[i][j]);
int ans = -INF;
for(int i = 1; i <= m; ++i)
{
for(int j = i; j <= m; ++j)
{
int colSum[100];
memset(colSum, 0, 100); //特别注意
for(int k = 1; k <= n; ++k)
for(int z = i; z <= j; ++z)
colSum[k] += maze[z][k];
//printf("%d\n", sumOfArray(colSum, n));
ans = max(ans, sumOfArray(colSum, n));
}
}
printf("%d\n", ans);
}
return 0;
}
2. 最长递增子序列（LIS）
#include <stdio.h>
#define max(x, y) x > y ? x : y
int dp[30];
int buf[30];
int main()
{
freopen("in.txt", "r", stdin);
int k;
while(scanf("%d", &k) != EOF)
{
for(int i = 0; i < k; ++i)
{
scanf("%d", &buf[i]);
dp[i] = 1;
}
for(int i = 1; i < k; ++i)
{
int tmax = 1;
for(int j = 0; j < i; ++j)
if(buf[j] >= buf[i])
tmax = max(tmax, dp[j] + 1);
dp[i] = tmax;
}
int ans = -1;
for(int i = 0; i < k; ++i)
{
if(dp[i] > ans)
ans = dp[i];
}
printf("%d\n", ans);
}
return 0;
}
3. 最长公共子序列（LCS）
#include <stdio.h>
#include <string.h>
#define max(x, y) x > y ? x : y
int dp[101][101];
char sa[101], sb[101];
int main()
{
freopen("in.txt", "r", stdin);
while(gets(sa))
{
gets(sb);
for(int i = 0; i < 101; ++i)
{
for(int j = 0; j < 101; ++j)
dp[i][j] = 0;
dp[0][i] = 0;
dp[i][0] = 0;
}
int lena = strlen(sa);
int lenb = strlen(sb);
for(int i = 1; i <= lena; ++i)
for(int j = 1; j <= lenb; ++j)
{
if(sa[i-1] == sb[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
printf("%d\n",dp[lena][lenb]);
}
return 0;
}
4. 0-1背包
// dp[i][j] = max(dp[i-1][j], dp[i-1][j-list[i].v]+list[i].v)
#include <stdio.h>
#define max(x, y) x > y ? x : y
struct Node{
int t, v;
}list[101];
int dp[101][1001];
int main()
{
freopen("in.txt", "r", stdin);
int T, M;
while(scanf("%d%d", &T, &M) != EOF)
{
for(int i = 0; i < 1001; ++i)
dp[0][i] = 0;
for(int i = 0; i < 101; ++i)
dp[i][0] = 0;
for(int i = 1; i <= M; ++i)
scanf("%d%d", &list[i].t, &list[i].v);
for(int i = 1; i <= M; ++i)
{
for(int j = T; j >= list[i].t; --j)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-list[i].t]+list[i].v);
for(int j = list[i].t-1; j >= 0; --j)
dp[i][j] = dp[i-1][j];
}
printf("%d\n", dp[M][T]);
}
return 0;
}
5. 完全背包
#include <stdio.h>
#include <string.h>
#define min(x, y) x < y ? x : y
#define INF 0x7fffffff
struct Node{
int p, w;
}list[501];
int dp[10001];
int main()
{
freopen("in.txt", "r", stdin);
int cases, e, f, n;
while(scanf("%d", &cases) != EOF)
{
while(scanf("%d%d%d", &e, &f, &n) != EOF)
{
int V = f - e;
for(int i = 1; i <= n; ++i)
scanf("%d%d", &list[i].p, &list[i].w);
for(int i = 1; i <= V; ++i)
dp[i] = INF;
dp[0] = 0;
for(int i = 1; i <= n; ++i)
for(int j = list[i].w; j <= V; ++j)
if(dp[j - list[i].w] != INF)
dp[j] = min(dp[j], dp[j-list[i].w] + list[i].p);
if(dp[V] != INF)
printf("%d\n", dp[V]);
else
puts("-1\n");
}
}
return 0;
}
6. 多重背包
#include <stdio.h>
#define max(x, y) x > y ? x : y
struct Node{
int price, weight;
}list[2002];
int dp[101];
int main()
{
freopen("in.txt", "r", stdin);
int c;
while(scanf("%d", &c) != EOF)
{
int n, m;
scanf("%d%d", &n, &m);
int size = 1;
while(m--)
{
int p, w, num;
scanf("%d%d%d", &p, &w, &num);
int k = 1;
while(num >= k)
{
list[size].price = k * p;
list[size].weight = k * w;
size++;
num -= k;
k *= 2;
}
if(num != 0)
{
list[size].price = num * p;
list[size].weight = num * w;
size++;
}
}
//for(int i = 1; i < size; ++i)
//printf("%d %d\n", list[i].price, list[i].weight);
for(int i = 0; i <= n; ++i)
dp[i] = 0;
for(int i = 1; i < size-1; ++i)
for(int j = n; j >= list[i].price; --j)
dp[j] = max(dp[j], dp[j-list[i].price] + list[i].weight);
printf("%d\n", dp[n]);
}
return 0;
}
7. 硬币兑换问题
题意：兑换100元零钱，有1、2、5、10元四种面值，共有多少种兑换方法？
#include <stdio.h>
#include <string.h>
int coins[4] = {1,2,5,10};
//递归
int exchange(int sum, int n)
{
if(sum < 0 || n == 0)
return 0;
if(sum == 0)
return 1;
return (exchange(sum, n-1)+exchange(sum-coins[n-1], n));
}
//动态规划
int dp[101]; // dp[i]表示i元零钱的兑换方法数，对于每一种面值，等于少一个该面值的方法数加上包含该面值后的方法数，类似于完全背包；注意：少了一个该面值，并不表示不再有该面值
int dpExchange(int n)
{
memset(dp, 0, 101);
dp[0] = 1;
for(int i = 0; i < 4; ++i)
for(int j = coins[i]; j <= n; ++j)
dp[j] = dp[j] + dp[j-coins[i]];
return dp[n];
}
int main()
{
printf("%d\n", exchange(100, 4));
printf("%d\n", dpExchange(100));
return 0;
}
