貪心算法——背包問題-創(chuàng)新互聯(lián)

14天閱讀挑戰(zhàn)賽

成都創(chuàng)新互聯(lián)企業(yè)建站,10年網(wǎng)站建設(shè)經(jīng)驗，專注于網(wǎng)站建設(shè)技術(shù)，精于網(wǎng)頁設(shè)計，有多年建站和網(wǎng)站代運營經(jīng)驗，設(shè)計師為客戶打造網(wǎng)絡(luò)企業(yè)風(fēng)格，提供周到的建站售前咨詢和貼心的售后服務(wù)。對于成都網(wǎng)站制作、成都網(wǎng)站建設(shè)中不同領(lǐng)域進行深入了解和探索，創(chuàng)新互聯(lián)在網(wǎng)站建設(shè)中充分了解客戶行業(yè)的需求，以靈動的思維在網(wǎng)頁中充分展現(xiàn)，通過對客戶行業(yè)精準(zhǔn)市場調(diào)研，為客戶提供的解決方案。

目錄

1.題目描述? ? ?

2.問題分析

3.算法設(shè)計

4.C++程序

5.算法復(fù)雜度及優(yōu)化

5.1算法復(fù)雜度分析

5.2算法優(yōu)化擴展

---

1.題目描述? ? ?

有n種物品，每種物品只有一個，第i種物品的重量為，價值為，背包的容量為W，物品可以分割。如何放置物品，使得背包的物品價值大？

i個物品重量及其價值如下：

物品清單

物品i	1	2	3	4	5	6	7	8	9	10
重量	4	2	9	5	5	8	5	4	5	5
價值	3	8	18	6	8	20	5	6	7	15

2.問題分析

? 由于物品可以分割，貪心策略選擇單位重量價值大的物品裝入背包最為合適。所以在選擇過程中需要將物品按照單位重量價值遞減的順序進行排序，以此取前面單位重量價值大的物品。

3.算法設(shè)計

? 1）將物品的重量、價值和單位重量價值定義為一種結(jié)構(gòu)體類型，方便對其按照單位重量價值從大到小進行排序。

? 2）根據(jù)貪心算法策略，以此取單位重量價值的大物品存入背包中，直至背包填滿，如果到達第i個物品時超出了背包容量，那么就取該物品其中的一部分放入背包中。

4.C++程序

#include#include
using namespace std;

struct item {
	double w;//物品重量
	double v;//物品價值
	double p;//物品單位重量價值(價值/重量)
};
bool cmp(item a, item b) {
	return a.p >b.p;
}
item s[1000];
int main() {
	int n;
	double sum = 0,w,wleft;
	wleft = w;
	cin >>w>>n;
	for (int i = 0; i< n; i++) {
		cin >>s[i].w >>s[i].v;
		s[i].p = s[i].v / s[i].w;
	}
	sort(s, s + n, cmp);
	for (int i = 0; i< n; i++) {
		if (s[i].w<= wleft) {
			wleft -= s[i].w;
			sum += s[i].v;
		}
		else {
			sum += wleft * s[i].p;
			break;
		}
	}
	system("pause");
	return 0;
}

5.算法復(fù)雜度及優(yōu)化 5.1算法復(fù)雜度分析

? （1）時間復(fù)雜度：程序運行時間主要耗費在對物品按照單位重量價值排序上，采用的C++頭文件algorithm中的sort方法，此方法采用快速排序，時間復(fù)雜度為O()。

? （2）空間復(fù)雜度：空間主要耗費在對物品的存儲上?？臻g復(fù)雜度為O(定義數(shù)組的大小)。

5.2算法優(yōu)化擴展

? 如果物品不可分割，那么使用該貪心算法是否可以得到最優(yōu)解呢？

? 物品可分割的背包問題稱為背包問題，物品不可分割的背包問題稱為0/1背包問題。0/1背包問題已經(jīng)不具備貪心選擇的性質(zhì)，并不能通過局部最優(yōu)達到全局最優(yōu)。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：貪心算法——背包問題-創(chuàng)新互聯(lián)
本文URL：http://bm7419.com/article4/igpoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、用戶體驗、軟件開發(fā)、Google、建站公司、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)