欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++與Java分別解決活動(dòng)選擇問(wèn)題和帶權(quán)活動(dòng)選擇問(wèn)題

 更新時(shí)間:2022年06月30日 10:06:45   作者:成就一億技術(shù)人  
這篇文章介紹了C++與Java分別解決活動(dòng)選擇問(wèn)題和帶權(quán)活動(dòng)選擇問(wèn)題,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮,它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。

活動(dòng)安排問(wèn)題

問(wèn)題描述: 設(shè)有n個(gè)活動(dòng)的集合E = {1,2,…,n},其中每個(gè)活動(dòng)都要求使用同一資源,如演講會(huì)場(chǎng)等,而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si < fi 。如果選擇了活動(dòng)i,則它在半開(kāi)時(shí)間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交,則稱(chēng)活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō),當(dāng)si >= fj或sj >= fi時(shí),活動(dòng)i與活動(dòng)j相容。

活動(dòng)選擇問(wèn)題代碼實(shí)現(xiàn)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
struct ActivityTime
{
public:
    ActivityTime (int nStart, int nEnd) 
        : m_nStart (nStart), m_nEnd (nEnd) 
    { }
    ActivityTime ()
        : m_nStart (0), m_nEnd (0)
    { }
    friend 
    bool operator < (const ActivityTime& lth, const ActivityTime& rth) 
    {
        return lth.m_nEnd < lth.m_nEnd ;
    }
public:
    int m_nStart ;
    int m_nEnd ;
} ;
class ActivityArrange 
{
public:
    ActivityArrange (const vector<ActivityTime>& vTimeList) 
    {
        m_vTimeList = vTimeList ;
        m_nCount = vTimeList.size () ;
        m_bvSelectFlag.resize (m_nCount, false) ;
    }
    // 活動(dòng)安排
    void greedySelector () 
    {
        __sortTime () ;
        // 第一個(gè)活動(dòng)一定入內(nèi)
        m_bvSelectFlag[0] = true ;    
        int j = 0 ;
        for (int i = 1; i < m_nCount ; ++ i) {
            if (m_vTimeList[i].m_nStart > m_vTimeList[j].m_nEnd) {
                m_bvSelectFlag[i] = true ;
                j = i ;
            }
        }
        copy (m_bvSelectFlag.begin(), m_bvSelectFlag.end() ,ostream_iterator<bool> (cout, " "));
        cout << endl ;
    }
private:
    // 按照活動(dòng)結(jié)束時(shí)間非遞減排序
    void __sortTime () 
    {
        sort (m_vTimeList.begin(), m_vTimeList.end()) ;
        for (vector<ActivityTime>::iterator ite = m_vTimeList.begin() ;
                ite != m_vTimeList.end() ; 
                ++ ite) {
            cout << ite->m_nStart << ", "<< ite ->m_nEnd << endl ;
        }
    }
private:
    vector<ActivityTime>    m_vTimeList ;    // 活動(dòng)時(shí)間安排列表
    vector<bool>            m_bvSelectFlag ;// 是否安排活動(dòng)標(biāo)志
    int    m_nCount ;    // 總活動(dòng)個(gè)數(shù)
} ;
int main()
{
    vector<ActivityTime> vActiTimeList ;
    vActiTimeList.push_back (ActivityTime(1, 4)) ;
    vActiTimeList.push_back (ActivityTime(3, 5)) ;
    vActiTimeList.push_back (ActivityTime(0, 6)) ;
    vActiTimeList.push_back (ActivityTime(5, 7)) ;
    vActiTimeList.push_back (ActivityTime(3, 8)) ;
    vActiTimeList.push_back (ActivityTime(5, 9)) ;
    vActiTimeList.push_back (ActivityTime(6, 10)) ;
    vActiTimeList.push_back (ActivityTime(8, 11)) ;
    vActiTimeList.push_back (ActivityTime(8, 12)) ;
    vActiTimeList.push_back (ActivityTime(2, 13)) ;
    vActiTimeList.push_back (ActivityTime(12, 14)) ;
    ActivityArrange aa (vActiTimeList) ;
    aa.greedySelector () ;
    return 0 ;
}

結(jié)果

帶權(quán)活動(dòng)選擇問(wèn)題

算法偽代碼【核心算法】

問(wèn)題描述:

會(huì)場(chǎng)出租:選擇出租的活動(dòng)時(shí)間不能沖突,怎樣選擇才能選更多的活動(dòng)?

帶權(quán)活動(dòng)選擇問(wèn)題代碼實(shí)現(xiàn)

package day1.java;
public class activityChoose {
    private static class Activity{
        int startTime;
        int endTime;
        int weight;
        private Activity(int startTime, int endTime, int weight){
            this.startTime = startTime;
            this.endTime = endTime;
            this.weight = weight;
        }
    }
    private static void activityChoose(Activity[] S){
        // 記錄p:在a_i開(kāi)始前最后結(jié)束的活動(dòng)
        int[] p = new int[S.length+1];
        p[0] = 0;
        p[1] = 0;
        for(int i=2; i<=S.length; i++){
            for(int j=i-1; j>0; j--){
                if(S[j-1].endTime <= S[i-1].startTime){
                    p[i] = j;
                    break;
                }
            }
        }
        for(int i=1; i<=S.length; i++){
            System.out.println(p[i]);
        }
        int[] D = new int[S.length+1];
        int[] Rec = new int[S.length+1];
        D[0] = 0;
        // 動(dòng)態(tài)規(guī)劃
        for(int j=1; j<S.length+1; j++){
            if(D[p[j]]+S[j-1].weight > D[j-1]){
                D[j] = D[p[j]] + S[j-1].weight;
                Rec[j] = 1;
            }else{
                D[j] = D[j-1];
                Rec[j] = 0;
            }
        }
        // 輸出方案
        int k=S.length;
        while(k > 0){
            if(Rec[k] == 1){
                System.out.println("選擇:開(kāi)始時(shí)間"+S[k-1].startTime+"結(jié)束時(shí)間"+S[k-1].endTime);
                k = p[k];
            }else{
                k--;
            }
        }
    }
    // 按結(jié)束時(shí)間從小到大排序
    private static void quickSortActivity(Activity[] S, int start, int end){
        int i = start;
        int j = end;
        if (start < end){
            Activity tmp = S[i];
            while(i<j){
                while(i<j && S[i].endTime <= S[j].endTime){
                    j--;
                }
                S[i] = S[j];
                while (i < j && S[i].endTime >= S[j].endTime) {
                    i++;
                }
                S[j] = S[i];
            }
            S[i] = tmp;
            quickSortActivity(S, start, i-1);
            quickSortActivity(S, i+1,end);
        }
    }
    public static void main(String[] args){
        Activity[] S = new Activity[10];
        S[0] = new Activity(1,4,1);
        S[1] = new Activity(3,5,6);
        S[2] = new Activity(0,6,4);
        S[3] = new Activity(4,7,7);
        S[4] = new Activity(3,9,3);
        S[5] = new Activity(5,9,12);
        S[6] = new Activity(6,10,2);
        S[7] = new Activity(8,11,9);
        S[8] = new Activity(8,12,11);
        S[9] = new Activity(2,14,8);
        quickSortActivity(S, 0, 9);
        activityChoose(S);
    }
}

結(jié)果

到此這篇關(guān)于C++與Java分別解決活動(dòng)選擇問(wèn)題和帶權(quán)活動(dòng)選擇問(wèn)題的文章就介紹到這了,更多相關(guān)C++活動(dòng)選擇內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 實(shí)例講解C語(yǔ)言編程中的結(jié)構(gòu)體對(duì)齊

    實(shí)例講解C語(yǔ)言編程中的結(jié)構(gòu)體對(duì)齊

    這篇文章主要介紹了C語(yǔ)言編程中的結(jié)構(gòu)體對(duì)齊,值得注意的是一些結(jié)構(gòu)體對(duì)齊的例子在不同編譯器下結(jié)果可能會(huì)不同,需要的朋友可以參考下
    2016-04-04
  • 史上最強(qiáng)C語(yǔ)言分支和循環(huán)教程詳解

    史上最強(qiáng)C語(yǔ)言分支和循環(huán)教程詳解

    這篇文章主要介紹了史上最強(qiáng)C語(yǔ)言分支和循環(huán)教程詳解,本文通過(guò)代碼演示給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-11-11
  • c語(yǔ)言main函數(shù)使用及其參數(shù)介紹

    c語(yǔ)言main函數(shù)使用及其參數(shù)介紹

    這篇文章主要介紹了c語(yǔ)言main函數(shù)使用及其參數(shù)介紹,需要的朋友可以參考下
    2014-04-04
  • 如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本

    如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本

    這篇文章主要介紹了如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本的方法,需要的朋友可以參考下
    2021-04-04
  • C++中CSimpleList的實(shí)現(xiàn)與測(cè)試實(shí)例

    C++中CSimpleList的實(shí)現(xiàn)與測(cè)試實(shí)例

    這篇文章主要介紹了C++中CSimpleList的實(shí)現(xiàn)與測(cè)試實(shí)例,較為詳細(xì)的講述了C++列表類(lèi)的實(shí)現(xiàn)方法,需要的朋友可以參考下
    2014-10-10
  • C++構(gòu)造函數(shù)深度學(xué)習(xí)

    C++構(gòu)造函數(shù)深度學(xué)習(xí)

    這篇文章主要為大家詳細(xì)介紹了C++構(gòu)造函數(shù),深度學(xué)習(xí)C++構(gòu)造函數(shù),感興趣的小伙伴們可以參考一下
    2016-08-08
  • C語(yǔ)言中動(dòng)態(tài)內(nèi)存分配malloc、calloc和realloc函數(shù)解析

    C語(yǔ)言中動(dòng)態(tài)內(nèi)存分配malloc、calloc和realloc函數(shù)解析

    C語(yǔ)言跟內(nèi)存申請(qǐng)相關(guān)的函數(shù)主要有 alloca、calloc、malloc、free、realloc等,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中動(dòng)態(tài)內(nèi)存分配malloc、calloc和realloc函數(shù)的相關(guān)資料,需要的朋友可以參考下
    2022-03-03
  • 最新評(píng)論