动态规划经典问题
1、三角数塔问题
设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以向左走或向右走,如图所示:
要求从根结点开始,请找出一条路径,使路径之和最大,只要输出路径的和。
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXN 101
int n,d[MAXN][MAXN];
int a[MAXN][MAXN];
void fnRecursive(int,int);
//递推方法函数声明
int fnMemorySearch(int,int);
//记忆化搜索函数声明
int main()
{
}
void fnRecursive(int i,int j)
//递推方法实现过程
{
}
int fnMemorySearch(int i,int j)
//记忆化搜索实现过程
{
}
2、硬币问题
问题描述:有n种硬币,面值分别为V1,V2,…,Vn, 每种有无限多。给定非负整数S,可以选用多少硬币,使得面值之和恰好为S,输出硬币数目的最小值和最大值。(1<=n<=100,0<=S<=10000,1<=Vi<=S)
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define INF 100000000
#define MAXNUM 10000
#define MONEYKIND 100
int n,S;
int V[MONEYKIND];
int min[MAXNUM],max[MAXNUM];
void dp(int*,int*);
//递推方法函数声明
void print_ans(int*,int);
//输出函数声明
int main()
{
}
void dp(int *min,int *max)
//递推过程实现
{
}
void print_ans(int *d,int S)
//输出函数实现
{
}
3、矩形嵌套问题
问题描述:有n个矩形,每个矩形可以用两个整数a,b描述,表示它的长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中,当且仅当a<c,b<d或者b<c,a<d(相当于把矩形X旋转90度)。例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)内。你的任务是选出尽量多的矩形排成一行,使得除了最后一个之外,每一个矩形都可以嵌套在下一个矩形内。
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 100//矩形的最大个数
struct Rect
{
};
int n;//矩形个数
struct Rect rect[MAXNUM];
int G[MAXNUM][MAXNUM];//邻接有向图
int d[MAXNUM];//过程数组
int dp(int i,int G[MAXNUM][MAXNUM]);
int main()
{
}
int dp(int i,int G[MAXNUM][MAXNUM])
{
}
4、求一组数列的最长的不下降序列。
问题描述:设有一个正整数序列b1,b2,b3,……,bn,若下标为i1<i2<i3,……<ik且有bi1≤bi2≤……bik则称存在一个长度为k的不下降序列。可能有多个不下降序列,输出最长序列的长度。
样例输出:5
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 100//最大数字个数
int b[MAXNUM][2];
int n;
int len;
int main()
{
}
5、0-1背包问题
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100//物品种类最大数量
int w[MAXN],V[MAXN];
int C;//最大容量
int n;//物品种类
int d[MAXN][MAXN];
int jMax;
int min(int,int);
//两数之间的最小值
int max(int,int);
//两数之间的最大值
void print_ans(int d[][MAXN],int,int);
//构造最优解并输出
int main()
{
}
int min(int x,int y)
{
}
int max(int x,int y)
{
}
6、数字游戏问题
小W发明了一个游戏,他在黑板上写出了一行数字a1,a2,a3,……,an,然后给你M个回合的机会,每回合你可以从中选择一个数字擦去它,接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合,所有你擦去的数字之和就是你所得的分数。
编程算算,对于每个a和b序列,可以得到的最大得分是多少。
输入样例:
输出样例:
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 100
int n;//数字个数
int m;//回合数
int Num[MAXNUM];//原始数据数组
int DescNum[MAXNUM];//递减数据数组
int F[MAXNUM][MAXNUM];//过程数组
void swap(int ,int );
//交换两个整数
int max(int ,int );
//取两个中的最大值
int main()
{
}
void swap(int x,int y)
{
}
int max(int x,int y)
{
}
7、挖地雷
在一个地图上有N个地窖(N<=200),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的。某人可以从任一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 200
int n;//地窖的个数
int w[MAXNUM];//每个地窖中的地雷数
int Sum[MAXNUM];//挖到的地雷总数
int G[MAXNUM][MAXNUM];//形成的图
int next[MAXNUM];//记录路径
int max;//最大值
int start;
//void init(int G[MAXNUM][MAXNUM]);
//void init2(int n[MAXNUM]);
int main()
{
}
8、最小代价子母树
设有n堆沙子排成一排,其编号为1,2,3,…,n(n≤100)。每堆沙子有一定的数量,如下表
现在要将n堆沙子归并成一堆。归并的过程为每次只能将相邻的两堆沙子堆成一堆,这样经过n-1次归并之后最后成为一堆,如上面7堆沙子,可以有多种方法归并成一堆,归并的代价是这样定义的,将两堆沙子归并为一堆时,两堆沙子数量的和称为归并2堆沙子的代价。由此可见,不同归并过程得到的总的归并代价是不一样的。
问题:n堆沙子的数量给出之后,找出一种合理的归并方法,使总的归并代价为最小。
[输入格式]
[输出格式]
输入样例:
7
13 7 8 16 21 4 18
输出样例:
239
【代码】
//
//
//
//
#include <STDIO.H>
#include <STDLIB.H>
#define INF 1000000
#define MAXNUM 100
int n;//沙子的堆数
int Num[MAXNUM];//每堆沙子的数量
int F[MAXNUM][MAXNUM];//过程函数
int G[MAXNUM][MAXNUM];
int fnMin(int ,int );
//返回两个数的最小值
int main()
{
}
9、数字移动问题
给出一个1到n的排列,每次可以移动一个数到一个任意位置。问要达到状态1,2,3……n至少移动多少次?
Sample Input
5
2 1 4 5 3
Sample Output
2
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 100//最大数字个数
#define INF 100000000
int n;//数字个数
int Num[MAXNUM];//未排序数字
int Last[MAXNUM];
void update(int x,int y,int L[],int N[],int i);
//递归函数
int main()
{
}
void update(int x,int y,int L[],int N[],int i)
{
}
10、叠放箱子问题
一、每个箱子上最多只能直接叠放一个箱子;
二、编号较小的箱子不能放在编号较大的箱子之上;
三、每个箱子都给出了自身重量与可承受重量,每个箱子之上的所有箱子重量之和不得超过该箱的可承受重量。
【输入】
【输出】
【样例】有五个箱子,如下表:
1
2
3
4
5
则最多可以叠放4个箱子,方案之一如:1、2、3、5
【代码】
//
//
//
#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 1000//最大的箱子个数
#define MAXWIGHT 3000//
int n;//箱子数目
int F[MAXNUM+1][6000];//第i个箱子到第n个箱子中总重量为j的最大箱子数
int Weight[MAXNUM];//箱子重量
int Capacity[MAXNUM];//箱子所能承受的压力
int max(int ,int );
//返回两个数的最大值
int main()
{
}
int max(int x,int y)
{
}
http://blog.sina.com.cn/s/blog_65caa9780100xrq6.html
http://www.cnblogs.com/wuyuegb2312/p/3281264.html
http://blog.csdn.net/lalor/article/details/6954923