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; }