word版可編輯-算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告—背包問題精心整理(已修改)
2025-04-05 05:17 本頁(yè)面
【正文】 算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告—0/1背包問題【問題描述】 給定n種物品和一個(gè)背包。物品i的重量是，其價(jià)值為，背包容量為C。問應(yīng)該如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？【問題分析】0/1背包問題的可形式化描述為：給定C0, 0, 0,，要求找出n元0/1向量，使得，而且達(dá)到最大。因此0/1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題。 【算法設(shè)計(jì)】設(shè)0/1背包問題的最優(yōu)值為m( i, j )，即背包容量是j，可選擇物品為i,i+1,…,n時(shí)0/1背包問題的最優(yōu)值。由0/1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m( i, j )的遞歸式如下： max{m( i+1, j ), m( i+1, j)+} m( i, j )= m(i+1,j) m(n,j)= 0 【算法實(shí)現(xiàn)】include include include int min(int w, int c) { int temp。 if (w c) temp = w。 else te
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1