实验3动态规划

实验3动态规划

实验二 贪心法（4学时）

上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。

（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。

（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。

一、实验目的与要求

1. 掌握动态规划法的基本思想方法；理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。

2. 了解适用于用动态规划法求解的问题类型，并能设计相应动态规划法算法；

3. 掌握动态规划算法复杂性分析方法分析问题复杂性。

二、实验内容（以下题目要求采用动态规划算法完成）：

1、找零钱问题

设有n 种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数j 的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j 时，记C(i,j)=∞。

设计一个动态规划算法，对1≤j ≤L ，计算出所有的C( n,j )。算法中只允许实用一个长度为L 的数组。用L 和n 作为变量来表示算法的计算时间复杂性

2、最大子段和问题

给定由n 个整数组成的序列(a1, a2, …, an)，求该序列形如 的子段和的最大值，

当所有整数均为负整数时，其最大子段和为0。如序列为（-20，11，-4，13，-5）其最大子段 和为20对应子段为 （11，-4，13）

3、数塔问题 有N 件物品和一个容量为V 的背包。第i 件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

三、实验步骤

1． 理解算法思想和问题要求；

2． 编程实现题目要求；

3． 上机输入和调试自己所编的程序；

∑=j i k k a ∑=42k k a

4．验证分析实验结果；

5．整理出实验报告。

四、实验要求

1）上述题目任选两道做。

2）独立完成程序代码的编写

3）独立完成实验及实验报告

附：实验报告的主要内容

一．实验目的

二．问题描述

三．解题思路

四．算法设计

包含：数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流程图等

五.程序调试及运行结果分析

六.实验总结

附录：程序清单（程序过长，只附主要部分）

五、实验原理

（一）、动态规划的基本思想：

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

二、设计动态规划法的步骤：

1、找出最优解的性质，并刻画其结构特征；

2、递归地定义最优值（写出动态规划方程）；

3、以自底向上的方式计算出最优值；

4、根据计算最优值时得到的信息，构造一个最优解。

步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。

三、动态规划问题的特征：

动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。

1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。（二）、动态规划算法的基本步骤

设计一个标准的动态规划算法，通常可按以下几个步骤进行： 1. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。

2. 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

3. 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。

4. 写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一

附注：部分实验代码

1、找零钱

for (i=0;i

{

for (j=i+1;j

if (T[i]>T[j])

{

Swap(T[i],T[j]);

}

}

long temptotal=total;

if (total>0)

for (i=kind-1;i>=0;i--)

{

Swap(T[i],T[kind-1]);

if (T[kind-1]>0)

{

c[kind-1]=temptotal/T[kind-1]; long tempcount=0;

while((c[kind-1]>0)&&(c[kind-1]<=mincount))

{

tempcount=c[kind-1];

temptotal=temptotal-T[kind-1]*c[kind-1];

for (j=kind-2;j>=0;j--)

if ((temptotal>0)&&(T[j]>0))

{

c[j]=temptotal/T[j];

temptotal=temptotal-T[j]*c[j];

tempcount=tempcount+c[j];

}

if

((tempcount>0)&&(tempcount

mincount=tempcount;

c[kind-1]=c[kind-1]-1;

temptotal=total;

tempcount=0;

}

}

}

2、最大子段和问题

void MaxSum(int n,int a[])

{

int sum=0;

int b=0;

for(int i=1;i<=n;i++)

{

if(b>0) b+=a[i];

else

b=a[i];

if(b>sum)

sum=b;

}

3、0-1背包问题

#include

#include

typedef struct

{

int object;

int weight;

int value;

}KnapSack;

KnapSack * knapsack; //背包数组，用malloc或new动态创建

int num; //物体的个数

int container; //背包的最大容量

int ** array=NULL; //用来存放子问题的结果

//动态创建背包

void Create_KnapSack()

{

char c;

printf("input the number of objects\n");

scanf("%d", &num);

knapsack=new KnapSack[num+1];

printf("input weight and value of %d objects, like 1:4 10\n",

num);

for(int i=1; i<=num; i++)

{ scanf("%d%c%d%c%d",&knapsack[i].object,&c,&knapsack[i].weight,&c,&knapsack[i].value);

getchar(); //为了获取空格或其他输入

}

int k= knapsack[num].value;

printf("%d",k);

printf("input the volume of the knapsack:\n");

scanf("%d", &container);

}

//确定最优子问题

void Resolve_KnapSack()

{

int k=knapsack[num].value;

printf("%d", k);

//创建动态二维数组m[num][container]

array=(int **)malloc((num+1)*sizeof(int *));

for(int i=0; i<=num; i++)

array[i]=(int *)malloc((container+1)*sizeof(int));

//

for(int j=0; j<=container; j++)

array[num][j] = (j>=knapsack[num].weight)?

knapsack[num].value : 0;

//子问题的最优结果

for(int m=num-1; m>0; m--)

for(int n=0; n<=container; n++)

if( n > knapsack[m].weight &&

array[m+1][n]<=array[m+1][n-

knapsack[m].weight]+knapsack[m].value)

array[m][n]=array[m+1][n-knapsack[m].weight]+knapsack[m].value;