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

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

目錄

1.題目描述? ? ?

2.問題分析

3.算法設(shè)計(jì)

4.C++程序

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

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

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

---

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.問題分析

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

3.算法設(shè)計(jì)

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

? 2）根據(jù)貪心算法策略，以此取單位重量價值的大物品存入背包中，直至背包填滿，如果到達(dá)第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ù)雜度：程序運(yùn)行時間主要耗費(fèi)在對物品按照單位重量價值排序上，采用的C++頭文件algorithm中的sort方法，此方法采用快速排序，時間復(fù)雜度為O()。

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

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

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

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

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

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

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

廣告

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