1：0-1背包
给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
输入格式:
共有n+1行输入：
第一行为n值和c值，表示n件物品和背包容量c；
接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。
输出格式:
输出装入背包中物品的最大总价值。
输入样例:
在这里给出一组输入。例如：
5 10 2 6 2 3 6 5 5 4 4 6
输出样例:
在这里给出相应的输出。例如：
15
#include <iostream> using namespace std; const int N = 1010; int n, m; int f[N]; int main() { cin >> n >> m; for (int i = 0; i < n; i ++ ) { int v, w; cin >> v >> w; for (int j = m; j >= v; j -- ) f[j] = max(f[j], f[j - v] + w); } cout << f[m]; return 0; }
2：01背包
事情是这样的，jzk要去爬山，但是他的包容量有限，可是他需要非常多的能量，要不然就很容易饿。
第一行给出jzk准备爬几次山。
每次爬山都会带新的包（因为jzk每用一个包都会被zwg抢过去），和准备新的食物（因为每次剩下来的都被zwg吃了）。
下一行给你这一次食物的数目n，和背包容量k，
接下来的一行给出n个食物的能量，再一行给出n个食物的大小（占背包的容量）。
请帮助jzk计算他最多可以带多少能量的食物去爬山。输出可以携带食物的最大能量和。
(n,m<1000) 能量和食物均小于40000
输入格式:
第一行包含整数T，表示有T组案例。
接着是T组案例，每组案例三行，第一行包含两个整数N，M，（N<=1000，M<=1000），表示物品数量和袋子的体积。第二行包含表示每个物品能量的n个整数。第三行包含代表每个物品体积的n个整数。
输出格式:
每组案例一行，只输出一个数字，表示jzk可以获得的最大能量。
输入样例:
在这里给出一组输入。例如：
1 5 10 1 2 3 4 5 5 4 3 2 1
输出样例:
在这里给出相应的输出。例如：
14
TIPS:
（包容量是10）可以带第2,3,4,5,个食物，2 + 3 +4 +5 = 14
#include <iostream> #include <cstring> using namespace std; const int N = 40010; int n, m; int f[N], w[N], v[N]; int main() { int T; cin >> T; while (T -- ) { memset(f, 0, sizeof f); // 初始化 cin >> n >> m; for (int i = 0; i < n; i ++ ) cin >> w[i]; for (int i = 0; i < n; i ++ ) cin >> v[i]; for (int i = 0; i < n; i ++ ) { for (int j = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]); } cout << f[m] << endl;; } return 0; }
3：最短路径条数（线性DP）
作者 夏仁强
单位 贵州工程应用技术学院
在一个m行n列的网格中，每个网格的各边的长度均相等，求由A(x1,y1)点到达B(x2,y2)点的最短路径条数，其中1<=m,n<=30。输入保证x2>=x1,y2>=y1
如有下图网格，起点和终点分别是A(1,1),B（2，3）
则最短路线是:
(1,1)->(1,2)->(1,3)->(2,3) (1,1)->(2,1)->(2,2)->(2,3) (1,1(->(1,2)->(2,2)->(2,3)
共3条最短路线
输入格式:
第一行输入网格的行数m和列数n
第二行输入A点的坐标
第三行输入B点的坐标
输出格式:
输出一个整数,表示从A点到达B点的最短路线条数
输入样例1:
6 7 1 1 2 3
输出样例1:
3
输入样例2:
30 30 1 1 30 30
输出样例2:
51542064
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
解析：
4：一步两步（线性DP）
作者 张洪旗
单位 海南师范大学
你要过河，但是没有桥，只有由一排石头堆成的石头路，你一次只能跨一个石头或者两个石头，求你到第n个石头有多少种走法。
输入格式:
正整数n
输出格式:
可能性的个数
输入样例1:
在这里给出一组输入。例如：
1
输出样例1:
在这里给出相应的输出。例如：
1
输入样例2:
在这里给出一组输入。例如：
2
输出样例2:
在这里给出相应的输出。例如：
2
输入样例1:
在这里给出一组输入。例如：
8
输出样例1:
在这里给出相应的输出。例如：
34
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include <iostream> using namespace std; const int N = 1010; int f[N]; int main() { f[1] = 1; f[2] = 2; int n; cin >> n; for (int i = 3; i <= n; i ++ ) f[i] = f[i - 1] + f[i - 2]; cout << f[n]; return 0; }
5：青蛙跳台阶
作者 房正华
单位 青岛工学院
一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
输入格式:
首先输入数字n，代表接下来有n组输入，50>=n>=0,然后每行一个数字，代表台阶数，数字为小于60的整数
输出格式:
对每一组输入，输出青蛙的跳法。
输入样例:
3 1 2 3
输出样例:
1 2 3
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include <iostream> using namespace std; const int N = 50; int f[N]; int main() { f[1] = 1; f[2] = 2; for (int i = 3; i <= 50; i ++ ) // 预处理 f[i] = f[i - 1] + f[i - 2]; int n; cin >> n; while (n -- ) { int x; cin >> x; cout << f[x] << endl; } return 0; }
6：数字三角形问题
作者 夏仁强
单位 贵州工程应用技术学院
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
输入格式:
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0…99之间。
输出格式:
输出数据只有一个整数，表示计算出的最大值。
输入样例:
在这里给出一组输入。例如：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出样例:
在这里给出相应的输出。例如：
30
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int n; int a[N][N], f[N][N]; int main() { cin >> n; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) cin >> a[i][j]; for (int i = 1; i <= n; i ++ ) f[n][i] = a[n][i]; for (int i = n - 1; i >= 1; i -- ) for (int j = 1; j <= i; j ++ ) f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j]; cout << f[1][1]; return 0; }
