算法合集之對(duì)擬陣的初步研究-在線瀏覽
2024-12-03 03:11本頁面
【正文】 擬陣，稱為圖擬陣 A B 第二部分：擬陣上的最優(yōu)化問題 問題提出 ? ?LSM ,?? ? ? ?? ?? Ux xwUw對(duì)于擬陣 S的元素 x有一個(gè)正整數(shù)權(quán)值 w(x) S的任意子集 U的權(quán)值 目標(biāo) :求權(quán)值最大獨(dú)立集。 ?該調(diào)度第 i個(gè)任務(wù)開始于時(shí)刻 i1,結(jié)束于時(shí)刻 i 表示第 i個(gè)任務(wù)的截止時(shí)刻 問題提出 :idnddd ,..., 21 ndi ??1n ,..., 21iw n個(gè) 整數(shù) ( ) , 表示第 i個(gè)任務(wù)的罰款 n個(gè)正整數(shù) 調(diào)度 : 0 1 2 3 4 5 2 3 1 3 :iw 9 7 6 8 罰款 :6+8=14 iw 如果任務(wù) i的結(jié)束時(shí)刻超過截止時(shí)刻 則要交付 的罰款。 id分析 ? 考慮這么一個(gè)問題：對(duì)于 S的子集 A，是否存在調(diào)度方案使 A中的任務(wù)都被完成。 調(diào)度 : 0 1 2 3 4 5 id1 2 4 3 擬陣結(jié)構(gòu) ? 對(duì)于給定的任務(wù)集合 A，能夠有效地判斷這些任務(wù)能否全部完成 ? 能全部完成的任務(wù)集合
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1