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

以你之姓@ 2023-09-29 15:34 16阅读 0赞

实验名称： 动态规划

一、实验预习

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 **）**。

算法描述：

![1f2661fc20404c0dafdeb1c5e2b85d1a.png][]

问题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**)**。

算法描述：

![924d00522f484159892564c36b5d61fc.png][]

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

![388f3b2f98f64b94ba7ca1042a651471.png][]

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

![b1d32302f4ed4ce9bad568d3d9b6683d.png][]![80e2bfe595c44d0e8c53cc87a260d414.png][]

3、实验结论

……………………（懒）……………………

[1f2661fc20404c0dafdeb1c5e2b85d1a.png]: https://img-blog.csdnimg.cn/1f2661fc20404c0dafdeb1c5e2b85d1a.png
[924d00522f484159892564c36b5d61fc.png]: https://img-blog.csdnimg.cn/924d00522f484159892564c36b5d61fc.png
[388f3b2f98f64b94ba7ca1042a651471.png]: https://img-blog.csdnimg.cn/388f3b2f98f64b94ba7ca1042a651471.png
[b1d32302f4ed4ce9bad568d3d9b6683d.png]: https://img-blog.csdnimg.cn/b1d32302f4ed4ce9bad568d3d9b6683d.png
[80e2bfe595c44d0e8c53cc87a260d414.png]: https://img-blog.csdnimg.cn/80e2bfe595c44d0e8c53cc87a260d414.png