首页 > 其他 > 详细

羊群过河问题

时间:2014-03-19 18:54:37      阅读:491      评论:0      收藏:0      [点我收藏+]

  一位牧民和一群数量为n的羊群,前方遇到一条小河,河边刚好有一条小船,假设小船足够大,可以一次载完所有羊,但是牧民会很累,船会划得很慢,但可以分批运过去:

  如果载一只羊过河,需要M(1)分钟 ;

  如果载两只羊过河,需要M(2)分钟 ;

  如果载三只羊过河,需要M(3)分钟 ;

  …………

  牧民空船返回对岸需要M分钟 ;

求得最短时间将所有的羊运到河对岸。

很像一道智力题,但在计算机看来,两步就可以得到答案。

下面给出我的思维过程:

  dp[n]  表示  把n只羊运送到河对岸需要的最少时间  ;

  如果只有一只羊需要过河 ,需要的时间 ,用 M + M(1) 来表示 ; 把 M + M(1) 的值赋给 dp[1] ;  

  如果有两只羊需要过河,先算出把两只羊一块载过去需要多长时间 ,用M + M(1) + M(2)来表示 ;

然后再算,先载一只过去,再把另外一只载过去需要多长时间,用dp[1] + dp[1] + m 来表示 ;

比较一下两种方法,哪种时间用的最少,把最少的赋值给dp[2] ;

  如果有三只羊需要过河,先算出把三只羊一块载过去需要多长时间,用M + M(1) + M(2) + M(3) 来表示 ;

然后再算,先载一只过去,再把另外两只载过去需要多长时间,用dp[1] + m + dp[2] 来表示 ;

然后再算,先载两只过去,再把另外一只载过去需要多长时间,用dp[2] + m + dp[1] 来表示 ;

比较一下三种方法,哪种时间用的最少,把最少的赋值给dp[3] ;

  …………     ;

  这样分析之后,很容易联想到用动态规划解题。(求全局最优解)

下面给出相关代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std ;
int main()  {
    int n ;
    cin >> n ;
    while(n--)  {
        int N , m ;
        cin >> N >> m ;
        int dp[1100] , i ;
        dp[0] = m ;
        for(i = 1 ; i <= N ; i++)    {
            int t ;
            cin >> t ;
            dp[i] = dp[i-1] + t ;
        }
        for(i = 2 ; i <= N ; i++)   
            for(int j = 1 ; j < i ; j++)
                if(dp[i] > ( dp[j] + dp[i - j] + m))
                    dp[i] = dp[j] + dp[i-j] + m ;
        cout << dp[N] << endl ;
    }
    return 0 ;
}

 

  

羊群过河问题,布布扣,bubuko.com

羊群过河问题

原文:http://www.cnblogs.com/scottding/p/3611342.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!