动态规划的应用
记忆化
给你一个数字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.
无论对于新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：
f[i][j]=a[i][j] + min{f[i+1][j]，f[i+1][j+1]}(a[i][j]表示当前状态,f[i][j]表示指标函数)
对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。
解决方法：
我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归函数: int f(int i, int j, int (*a)[4]){ int f1, f2, tmp=0, k; if(i==0||j==0) return a[0][0]; if(j==i) { for(k=0;k<=i;k++) tmp+=a[k][k]; return tmp; } f1=f(i-1, j, a); f2=f(i-1, j-1, a); if(f1<f2) return f2+a[i][j]; else return f1+a[i][j];}显而易见，这个算法就是最简单的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的。
并且记忆搜索占的内存相对来说较少。
计算核心片段： for(inti=n-1;i>=1;--i)//从倒数第二行开始{ for(intj=1;j<=i;j++) { if(a[i+1][j][1]>a[i+1][j+1][1])//左边大 { a[i][j][2]=0;//选择左边 a[i][j][1]+=a[i+1][j][1]; } else//右边大 { a[i][j][2]=1;//选择右边 a[i][j][1]+=a[i+1][j+1][1]; }练习题
USACO2.2 Subset Sums
题目如下：
对于从1到N的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。
举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：
{3}and {1,2}
这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）
如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:
{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。
PROGRAM NAME: subset
INPUT FORMAT
输入文件只有一行，且只有一个整数N
SAMPLE INPUT (file subset . in)
7
OUTPUT FORMAT
输出划分方案总数，如果不存在则输出0。
SAMPLE OUTPUT (file subset.out)
4
参考程序如下（C++语言）： #include<fstream>usingnamespacestd;constunsignedintMAX_SUM=1024;intn;unsignedlonglongintdyn[MAX_SUM];ifstreamfin(subset.in);ofstreamfout(subset.out);intmain(){fin>>n;fin.close();ints=n*(n+1);if(s%4){fout<<0<<endl;fout.close();return0;}s/=4;inti,j;dyn[0]=1;for(i=1;i<=n;i++)for(j=s;j>=i;j--)if(j-i>0){dyn[j]+=dyn[j-i];}fout<<(dyn[s]/2)<<endl;fout.close();return0;}USACO2.3LongestPrefix题目如下：
在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。
如果一个集合 P 中的元素可以通过并运算（允许重复；并，即∪，相当于 Pascal 中的 “+” 运算符）组成一个序列 S ，那么我们认为序列 S 可以分解为 P 中的元素。并不是所有的元素都必须出现。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：
{A, AB, BA, CA, BBC}
序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。
PROGRAM NAME: prefix
INPUT FORMAT
输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ，长度为 1..200,000 ，用一行或者多行的字符串来表示，每行不超过 76 个字符。换行符并不是序列 S 的一部分。
SAMPLE INPUT (file prefix. in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行，输出一个整数，表示 S 能够分解成 P 中元素的最长前缀的长度。
SAMPLE OUTPUT (file prefix.out)
11
示例程序如下：
#include <stdio.h>
#define MAXP 200
#define MAXL 10
char prim[MAXP+1][MAXL+1];
int nump;
int start[200001];
char data[200000];
int ndata;
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv,lv2, lv3;
if ((fin = fopen(prim. in, r)) == NULL)
{
perror (fopen fin);
exit(1);
}
if((fout = fopen(prim.out, w)) == NULL)
{
perror (fopen fout);
exit(1);
}
while (1)
{
fscanf (fin, %s, prim[nump]);
if (prim[nump][0] != '.')
nump++;
else
break;
}
ndata = 0;
while (fscanf (fin, %s, data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{
best = lv;
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] == data[lv+lv3]; lv3++)
if (!prim[lv2][lv3])
start[lv + lv3] = 1;
}
}
if (start[ndata])
best = ndata;
fprintf (fout, %i\n, best);
return 0;
}
动态规划作为一种重要的信息学竞赛算法，具有很强的灵活性。以上提供的是一些入门练习题，深入的学习还需要逐步积累经验。
解决0-1背包问题时使用动态规划的实现（c++）
#include <stdio.h>
typedef struct Object{
int weight;
int value; // float rate;
}
Object;
Object * array; //用来存储物体信息的数组
int num; //物体的个数
int container; //背包的容量
int ** dynamic_table; //存储动态规划表
bool * used_table; //存储物品的使用情况
//ouput the table of dynamic programming, it's for detection
void print_dynamic_table(){
printf(动态规划表如下所示:\n);
/* for(int j=0; j<=container; j++) printf(%d ,j); printf(\n);*/
for(int i=1; i<=num; i++) {
for(int j=0; j<=container; j++)
printf(%d ,dynamic_table[i][j]);
printf(\n);
}
}
//打印动态规划表
void print_array(){
for(int i=1; i<=num; i++)
printf(第%d个物品的重量和权重:%d %d\n,i,array[i].weight,array[i].value);
}
//打印输入的物品情况//插入排序，按rate=value/weight由小到大排//动态规划考虑了所有情况，所以可以不用排序
/*void sort_by_rate(){
for(int i=2; i<=num; i++) {
Object temp=array[i];
for(int j=i-1; j>=1; j--)
if(array[j].rate>temp.rate)
array[j+1]=array[j];
else break;
array[j+1]=temp;
}}*/
void print_used_object(){
printf(所使用的物品如下所示:\n);
for(int i=1; i<=num; i++)
if(used_table[i]==1)
printf(%d-%d\n, array[i].weight, array[i].value);
}
//打印物品的使用情况
/* 做测试时使用
void print_used_table(bool * used_table){
printf(used table as follows:\n);
for(int i=1; i<=num; i++)
printf(object %d is %d, i, used_table[i]);
}*/
void init_problem(){
printf(输入背包的容量:\n);
scanf(%d, &container);
printf(输入物品的个数:\n);
scanf(%d, &num);
array=new Object[num+1];
printf(输入物品的重量和价值, 格式如：4-15\n);
for(int i=1; i<=num; i++) {
char c;
scanf(%d%c%d, &array[i].weight, &c, &array[i].value);
// array[i].rate=array[i].value/array[i].weight;
}
print_array();
}
//对物体的使用情况进行回查
void trace_back(){
int weight=container;
used_table=new bool[num+1];
for(int i=1; i<=num; i++) used_table[i]=0;
//initalize the used_table to be non-used
for(int j=1; j<num; j++) {
//说明物品j被使用
if(dynamic_table[j][weight]!=dynamic_table[j+1][weight]) {
weight-=array[j].weight;
used_table[j]=1;
}
// print_used_table(used_table);
}
//检测第num个物品是否被使用
if(weight>=array[num].weight)
used_table[num]=1;
}
void dynamic_programming(){
dynamic_table=new int * [num+1];
for(int k=1; k<=num; k++)
dynamic_table[k]=new int[container+1];
//dynamic_programming table
//为二维动态规划表分配内存
for(int m=1; m<num; m++)
for(int n=0; n<=container; n++)
dynamic_table[m][n]=0;
int temp_weight=array[num].weight;
for(int i=0; i<=container; i++)
dynamic_table[num][i]=i<temp_weight?0:array[num].value;
//初始化动态规划表
for(int j=num-1; j>=1; j--) {
temp_weight=array[j].weight;
int temp_value=array[j].value;
for(int k=0; k<=container; k++)
if(k>=temp_weight && dynamic_table[j+1][k] < dynamic_table[j+1][k-temp_weight]+temp_value)
dynamic_table[j][k]=dynamic_table[j+1][k-temp_weight]+temp_value;
else dynamic_table[j][k]=dynamic_table[j+1][k];
}//构建动态规划表
print_dynamic_table();//打印动态规划表
}
void main(){
init_problem();
dynamic_programming();
trace_back();
print_used_object();
}
卓导
2024-11-20 广告
