資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Go語言實現加權區間排程演算法
加權區間排程問題圍繞著一組區間展開，每個區間都具有相關的權重。在本文中，我們將使用兩種方法（遞迴和動態規劃）在Go語言中實現加權區間排程演算法。這個經典的最佳化問題涉及選擇總權重最大的不重疊區間。
解釋
遞迴方法
遞迴方法採用了一種直接而優雅的方法。它逐個檢查每個區間，並考慮兩種情況——是否包含當前區間或跳過它。此方法利用遞迴來探索所有可能的區間組合，計算最大權重。雖然概念清晰，但由於存在子問題重疊，對於較大的輸入，它可能不是最有效的方法。
動態規劃方法
動態規劃方法是對遞迴方法的最佳化。它利用記憶化原則，儲存先前計算的結果以避免冗餘計算。此方法構建一個針對各種區間大小的最大權重表，並利用這些預先計算的值來有效地計算解決方案。它比遞迴方法更有效，尤其是在處理大型資料集時。
語法
func recursiveWeightedIntervalScheduling(intervals []Interval) int
語法以區間切片作為輸入並返回一個整數。它使用遞迴方法來查詢不重疊區間的最大總權重。此方法遞迴地探索所有可能的區間組合，並選擇總權重最高的組合。但是，由於冗餘計算，對於大量區間，它的效率可能較低。
演算法
根據區間的結束時間按升序排序區間。
初始化大小為len(intervals)+1的動態規劃表DP，其中DP[i]表示直到第i個區間的最大不重疊區間總權重。
將DP[0]設定為0，因為沒有區間需要考慮。
迭代intervals中的每個區間i（從1開始）——
使用二分查詢或線性查詢找到最後一個相容區間j（其中j的結束時間小於或等於i的開始時間）。
計算包含當前區間i以及DP[j]的總權重，並將其賦值給DP[i]。
將DP[i]更新為DP[i]和DP[i-1]之間的最大值，以考慮排除當前區間的可能性。
不重疊區間的最大總權重將儲存在DP[len(intervals)]中。
示例1
在這個例子中，我們有六個加權區間，表示為開始時間、結束時間和相應的權重的集合。目標是找到不重疊區間的最大總權重，即選擇一個區間子集，使得沒有兩個區間在時間上重疊，並且它們的權重之和最大化。Go語言中的遞迴加權區間排程演算法透過遞迴地探索所有可能的區間組合並選擇總權重最高的組合來有效地解決這個問題。
package main
import "fmt"
type Interval struct {
start, finish, weight int
}
func schedule(intervals []Interval, currentIndex, prevFinish int) int {
if currentIndex == len(intervals) {
return 0
}
if intervals[currentIndex].start < prevFinish {
return schedule(intervals, currentIndex+1, prevFinish)
}
includeCurrent := intervals[currentIndex].weight + schedule(intervals, currentIndex+1, intervals[currentIndex].finish)
skipCurrent := schedule(intervals, currentIndex+1, prevFinish)
return max(includeCurrent, skipCurrent)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
intervals := []Interval{
{1, 4, 3},
{3, 7, 5},
{0, 6, 8},
{5, 9, 2},
{8, 12, 6},
{10, 15, 4},
}
maxWeight := schedule(intervals, 0, 0)
fmt.Println("Maximum total weight of non-overlapping intervals:", maxWeight)
}
func sortByFinish(intervals []Interval) {
n := len(intervals)
for i := 0; i < n-1; i++ {
for j := 0; j < n-i-1; j++ {
if intervals[j].finish > intervals[j+1].finish {
intervals[j], intervals[j+1] = intervals[j+1], intervals[j]
}
}
}
}
輸出
Maximum total weight of non-overlapping intervals: 14
示例2
在這個例子中，我們有六個加權區間：[1, 4, 3]，[3, 5, 2]，[0, 6, 4]，[5, 7, 1]，[8, 9, 3]和[5, 9, 5]。Go語言中的動態規劃加權區間排程演算法用於查詢不重疊區間的最大總權重。對於給定的輸入區間，發現不重疊區間的最大總權重為14。
package main
import (
"fmt"
"sort"
)
type Interval struct {
start, end, weight int
}
func latestNonOverlapping(intervals []Interval, i int) int {
for j := i - 1; j >= 0; j-- {
if intervals[j].end <= intervals[i].start {
return j
}
}
return -1
}
func findMaxWeight(intervals []Interval) int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i].end < intervals[j].end
})
n := len(intervals)
dp := make([]int, n)
dp[0] = intervals[0].weight
for i := 1; i < n; i++ {
nonOverlap := latestNonOverlapping(intervals, i)
if nonOverlap != -1 {
dp[i] = max(dp[i-1], dp[nonOverlap]+intervals[i].weight)
} else {
dp[i] = max(dp[i-1], intervals[i].weight)
}
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
intervals := []Interval{
{1, 4, 3},
{3, 5, 2},
{0, 6, 4},
{5, 7, 1},
{8, 9, 3},
{5, 9, 5},
}
maxWeight := findMaxWeight(intervals)
fmt.Println("Maximum total weight of non-overlapping intervals:", maxWeight)
}
輸出
Maximum total weight of non-overlapping intervals: 8
現實生活中的應用
專案管理
加權區間排程用於專案排程，其中任務具有不同的重要性和時間範圍。透過選擇一系列具有最大組合重要性和無重疊的任務，該演算法幫助專案經理最佳化任務執行，以獲得更好的專案成果。
會議室預訂
在企業環境中，安排會議或研討會等活動至關重要。加權區間排程有助於高效地優先安排和安排活動，確保重要活動得到安排，最佳化會議室的資源使用。
結論
在本文中，我們研究了使用兩種方法（遞迴和動態規劃）的加權區間排程演算法。遞迴方法使用遞迴來探索所有可能的區間組合，而動態規劃方法儲存中間結果以提高效率。
瀏覽量：159
