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