天天看點

java 貪心算法 活動安排問題(詳細注釋)問題描述:活動安排問題--貪心算法具體實作代碼及詳細注釋

問題描述:活動安排問題--貪心算法

    有11項考試要安排,每項活動 i 的開始時間為 

java 貪心算法 活動安排問題(詳細注釋)問題描述:活動安排問題--貪心算法具體實作代碼及詳細注釋

(start),結束時間為

java 貪心算法 活動安排問題(詳細注釋)問題描述:活動安排問題--貪心算法具體實作代碼及詳細注釋

(finish)

    問在規定的時間内最多可安排多少項活動?

具體實作代碼及詳細注釋

public class ActivityArrange {

        /*
        解決方案代碼:
        i    表示 第i個活動
        s[i] 表示 第i個活動的開始時間
        f[i] 表示 第i個活動的結束時間
        a[i] 是否選擇安排第i個活動(true代表是,false代表否)
        */
        public static void greedySelector(int[] s, int[] f, boolean[] a)
        {
            a[1] = true;		// 選擇安排活動1
            int j = 1;		// 記錄最近一次的活動序号
            int count = 1;		// 總的可以安排的活動數

            int n = s.length - 1;
            for(int i=2; i<=n; i++)	// 依次檢查其餘每一項活動與已選擇的活動的相容性
            {
                if(s[i] >= f[j])	// 如果第i項活動相容
                {
                    a[i] = true;	// 選擇安排第i項活動
                    j = i;		// 記錄最近一次的活動序号
                    count++;	// 總的可以安排的活動數加1
                }
                else			// 如果不相容
                    a[i] = false;	// 選擇不安排第i項活動
            }

            // 列印 活動安排情況,安排的數量
            for (int i=1; i<a.length; i++)
                System.out.println("A" + i + " = " + a[i]);
            System.out.println("總的活動數量 = " + count);
        }

        public static void main(String[] args)
        {
            // 定義11項活動的開始時間,結束時間(按升序排序)
            int[] s = {0,1,3,0,5,3,5,6, 8, 8, 2, 12};// s[0]不用
            int[] f = {0,4,5,6,7,8,9,10,11,12,13,14};// f[0]不用
            boolean[] a = new boolean[12];// a[0]不用

            // 調用貪心算法 安排活動 并 計算最大可安排數量
            greedySelector(s, f, a);

        }
}
           
java 貪心算法 活動安排問題(詳細注釋)問題描述:活動安排問題--貪心算法具體實作代碼及詳細注釋