租用游艇问题石子合并问题动态规划实验-Toy模板网

这篇具有很好参考价值的文章主要介绍了租用游艇问题石子合并问题动态规划实验。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

实验名称：动态规划

一、实验预习

1、实验目的

1. 理解并掌握动态规划方法的设计思想；

2. 提高应用动态规划方法解决问题和设计算法的能力；

3. 通过编程实现租用游艇问题和石子合并问题，进一步理解动态规划方法解题的四个基本步骤。

2、实验内容

1. 租用游艇问题：长江游艇俱乐部在长江上设置了 n 个游艇出租站 1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i, j), 1≤i<j≤n。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。

两个测试用例：输入数据分别由文件名为 input 1.txt和input 2.txt的文本文件提供，文件的第一行中有 1 个正整数 n（n<=200），表示有 n个游艇出租站。接下来的 n-1 行是 r(i, j), 1≤i<j≤n。请分别计算并给出结果。

2. 石子合并问题：在一个操场上一排地摆放着 n 堆石子。要求将这些石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将 n 堆石子合并成一堆的最小得分。

两个测试用例：输入数据分别由文件名为 input 1.txt和input 2.txt的文本文件提供，文件的第一行有 1 个正整数 n，表示石子的堆数。第二行有 n 个数，分别表示每堆石子的个数。

3、硬、软件环境

计算机型号：Windows 11版81FW

编程语言：C++

开发工具：Dev-C++

4、实验预备工作

设计思想：

与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，不同的是会保存已解决的子问题的答案，从而在需要时再找出已求得的答案，这样就可以避免大量重复的计算了。

适用条件：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

（3）不满足分治策略的子问题相互独立的条件，也就是相邻子问题并不是相互独立的，而是相互有联系的；

（4）利用该问题分解出的子问题的解可以合并为该问题的解；

基本要素：

问题可被分解；具有最优子结构；子问题不是相互独立的；

解题步骤：

（1）最优子结构性质：找出最优解的性质，并刻划其结构特征。

（2）建立递归关系：递归地定义最优值。

（3）计算最优值：以自底向上的方式计算出最优值。

（4）构造最优解：根据计算最优值时得到的信息，构造最优解。

二、实验报告

1、实验步骤

问题1：

问题分析：要求出租站1到出租站n的所需要的最少租金，我们可以将问题变成

求出租站1到出租站i所需要的租金加上出租站i到出租站n的租金之和最少的问题，然后对出租站1到出租站i，和出租站i到出租站n再用同样的方法进行拆分，直到拆分到不可再分为止。

设计思想：用一个数组min_r[j]来储存第一站到第j站的最小租金，初始值为出租站1直接到出租站j的租金（1 < j <= n）。明显出租站1到出租站1的min_r[1]=0；出租站1到出租站2不可分，所以min_r[2]=r[1][2];从出租站3及以后的出租站i，min_r[i]=min（min_r[j]+r[j][i],其中 1 < j < i ）。

算法描述：

租用游艇问题石子合并问题动态规划实验

问题1：

问题分析：求n堆合并得分最小也就是求n-1堆的最小得分加剩下的那一堆的分数；而n-1堆石子的最小得分又可分成n-2堆的最小得分和剩下一堆的分数；……一直分到n-(n-2)小堆石子“合并”加剩下另一堆的分数。

设计思想：设二维数组sum[i][j]表示第i堆石头到第j堆石子的总和，二维数组dp[i][j]表示从第i堆到第j堆石头合并的最小得分数，当只有一堆石子“合并”时(i = j)，最小得分就是该小堆石子的数量，dp[i][j]=0；当相邻两堆合并时，最小得分也只有一种情况，dp[i][j]=0+sum[i][j]；当三堆及以上合并时，dp[i][j]= min( dp[i][k]+dp[k+1][j]+sum[i][j],其中i< k <j)。

算法描述：

租用游艇问题石子合并问题动态规划实验

2、实验结果

问题1：

#include<iostream>
using namespace std;
int r[200][200];
int main(){
int n;
cin>>n;
int min_r[200];
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
                 cin>>r[i][j];
         }
}
min_r[1]=0;
         for(int j=2;j<=n;j++){
                 min_r[j]=r[1][j];
         }
for(int i=3;i<=n;i++){
         for(int j=1;j<i;j++){
        if(min_r[i]>min_r[j]+r[j][i]){
                  min_r[i]=min_r[j]+r[j][i];
                  }
         }
}
cout<<min_r[n]<<endl;
}

租用游艇问题石子合并问题动态规划实验

问题2：

#include<iostream>
using namespace std;
int main()
{
   int n;
   cin>>n;
   int aa[n],sum[n][n],dp[n][n];
    for (int i=0; i<n; i++) {
        cin>>aa[i];     
    }  
    for (int i=0;i<n;i++) {    
        for (int j=i;j<n;j++) {
            dp[i][j]=999999;
            if (i==j)
                sum[i][j]=aa[i];    
            else
                sum[i][j]=sum[i][j-1]+aa[j];
        } 
    }              
    for (int i=0;i<n;i++) {
        dp[i][i]=0; 
        if (i<n-1)
            dp[i][i+1]=sum[i][i+1];
    }           
    for(int i=0;i<n-1;i++){
         for(int j=i+2;j<n;j++){
              for(int k=i;k<=j;k++)
                   if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[i][j]){
                       dp[i][j]=dp[i][k]+dp[k+1][j]+sum[i][j];
              }       
         }
    }
   cout<<"最小得分："<<dp[0][n-1]<<endl;
}

租用游艇问题石子合并问题动态规划实验