14天閱讀挑戰(zhàn)賽
努力是為了不平庸~
算法學(xué)習(xí)有些時候是枯燥的，這一次，讓我們先人一步，趣學(xué)算法！

???一名熱愛Java的大一學(xué)生，希望與各位大佬共同學(xué)習(xí)進(jìn)步??

??個人主頁：@周小末天天開心

各位大佬的點贊?? 收藏? 關(guān)注?，是本人學(xué)習(xí)的最大動力

感謝！

??該篇文章收錄專欄—趣學(xué)算法

目錄

題目描述

問題分析

算法設(shè)計?

完美圖解

算法詳解

（1）確定合適的數(shù)據(jù)結(jié)構(gòu)。

（2）對物體按單位重量價值進(jìn)行排序。

（3）使用貪心算法求解問題

算法分析

題目描述

????????有n種物品，每種物品只有一個，第i種物品的重量為 wi，價值為 vi，背包的容量為 w，物品可以分割。如何放置物品，使裝入背包的物品價值之和最大?

問題分析

（1）每次選擇價值最大的物品裝入背包。

（2）每次選擇重量最小的物品裝入背包。

（3）每次選擇單位重量價值最大的物品轉(zhuǎn)入背包。

??????? 思考一下，如果選價值最大的物品，但重量非常大，則可能一個也裝不下，分割一部分裝入，價值未必是最高的；如果選重量最小的物品裝入，則其價值不一定高，所以在總重量受到限制的情況下無法保證價值最大；而如果每次選單位重量價值最大的物品，則裝滿背包后一定能得到最大價值。

??????? 因此，我們應(yīng)采用第三種貪心策略——每次從剩下的物品中選單位重量價值最大的物品。

算法設(shè)計?

（1）確定合適的數(shù)據(jù)結(jié)構(gòu)并初始化。首先將物品的重量、價值和單位重量價值定位為一種結(jié)構(gòu)體類型，然后對物品按單位重量價值從大到小進(jìn)行排序。

（2）根據(jù)貪心策略，按照單位重量價值從大到小選取物品，直到達(dá)到背包容量。如果在裝入第 i 個物品時超出背包容量，則取該物品的一部分裝入背包。

完美圖解

??????? 物品的價值和重量如表2-3所示。如果背包容量 w = 30，怎么才能裝入最大價值的物品？

??????????????????????????????????????????????????????????????? 物品清單

（1）貪心策略是每次選單位重量價值（價值/重量）大的物品，因此可以按單位重量價值對物品進(jìn)行降序排列，排序后的物品清單如下所示：

???????????????????????????????????????????????????????? 排序后的物品清單

?（2）按照貪心策略，每次選擇單位重量價值大的物品裝入背包。

（3）構(gòu)造最優(yōu)解

算法詳解

（1）確定合適的數(shù)據(jù)結(jié)構(gòu)。

struct node {
    double w; //每種物品的重量
    double v; //每種物品的價值
    double p; //每種物品的單位重量價值（價值/重量）
}

（2）對物體按單位重量價值進(jìn)行排序。

bool cmp(node a, node b) { //自定義比較函數(shù)cmp
    return a.p > b.p; // 指定按照物品的單位重量價值進(jìn)行降序排列
}
sort(s, s + n, cmp); //前兩個參數(shù)分別為待排序數(shù)組的首地址和尾地址，cmp為比較函數(shù)

（3）使用貪心算法求解問題

double solve (int n, double w) {
    double sum = 0.0;    //sum表示已經(jīng)裝入物品的價值之和
    double cleft = w;    //背包的剩余容量
    for(int i = 0; i < n; i++) {    //是用貪心算法求解問題
        if(s[i].w < cleft) {    //如果物品的重量小于或等于剩余容量
            cleft -= s[i].w;
            sum += s[i].v;
        }
        else {    //如果物品的重量大于剩余容量
            sum += cleft * s[i].p;    //部分裝入
            break;
        }
    }
    return sum;
}

算法分析

（1）時間復(fù)雜度：時間主要耗費在對物品按單位重量價值進(jìn)行排序上，一般采用快速排序法，時間復(fù)雜度為O(nlogn)。

（2）空間復(fù)雜度：空間主要消耗在存儲物品的單位重量價值上，空間復(fù)雜度為O(n)。 ??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? ??????文章來源地址http://www.zghlxwxcb.cn/news/detail-430790.html

到了這里，關(guān)于【趣學(xué)算法】Day3 貪心算法——背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！