




已閱讀5頁,還剩2頁未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
海南大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告課程名稱:算法實(shí)驗(yàn) 班級: 物聯(lián)2班 姓名: 蔣煜輝 日期 15.11.21 實(shí)驗(yàn)題目:背包問題實(shí)驗(yàn)?zāi)康模赫莆談?dòng)態(tài)規(guī)劃、貪心算法的原理,并能夠按其原理編程實(shí)現(xiàn)解決背包問題,以加深對上述方法的理解。實(shí)驗(yàn)內(nèi)容:一個(gè)旅行者準(zhǔn)備隨身攜帶一個(gè)背包. 可以放入背包的物品有n 種, 每種物品的重量和價(jià)值分別為 wj , vj . 如果背包的最大重量限制是 b, 怎樣選擇放入背包的物品以使得背包的價(jià)值最大?目標(biāo)函數(shù):約束條件:線性規(guī)劃問題 由線性條件約束的線性函數(shù)取最大或最小的問題整數(shù)規(guī)劃問題 線性規(guī)劃問題的變量 xj 都是非負(fù)整數(shù)Fk(y):裝前 k 種物品, 總重不超過 y, 背包的最大價(jià)值i(k,y):裝前 k 種物品, 總重不超過 y, 背包達(dá)最大價(jià)值時(shí)裝入物品的最大標(biāo)號(hào)遞推方程、邊界條件、標(biāo)記函數(shù)實(shí)例計(jì)算:v1 = 1, v2 = 3, v3 = 5, v4 = 9, w1 = 2, w2 = 3, w3 = 4, w4 = 7, b = 10 Fk(y) 的計(jì)算表如下:K/y1234567891010112233445201334667993013556810101140135569101012實(shí)驗(yàn)步驟: 1、分析題目; 2、打開NetBeans軟件,新建一個(gè)名叫 Knapsackdxj的項(xiàng)目,并對其進(jìn)行保存; 3在新建的項(xiàng)目下對我們所分析的題目進(jìn)行編寫; 4、調(diào)試所編寫的程序; 5、運(yùn)行文件,并對其進(jìn)行測試,看是否正確。實(shí)驗(yàn)結(jié)果:實(shí)驗(yàn)小結(jié):在做本次實(shí)驗(yàn)之前,自己對動(dòng)態(tài)規(guī)劃、貪心算法的原理不是非常的理解,花了很多時(shí)間看了課本上的相關(guān)內(nèi)容。當(dāng)你懂得算法的基本原理后,再參考老師所提供的代碼進(jìn)行完善補(bǔ)充,必須結(jié)合算法的實(shí)際情況對代碼中的相關(guān)變量進(jìn)行修改,這樣才能充分利用課本所提供的代碼完成本次實(shí)驗(yàn)。通過本次試驗(yàn),自己基本上掌握上述算法解背包問題的原理,達(dá)到實(shí)驗(yàn)的目的。實(shí)驗(yàn)代碼:Knapsack.Javapackage chap4;import java.util.Scanner;/* * * author Jinyu */public class Knapsack /*常量定義* static final int MAX_NUM = 20; static final int MAX_WEIGHT = 100;/*自定義數(shù)據(jù)結(jié)構(gòu)* /*題目描述中的變量* private final int weight = new intMAX_NUM; private final int value = new intMAX_NUM; private final int x = new intMAX_NUM; private final int m = new intMAX_NUMMAX_NUM; private final int s = new intMAX_NUMMAX_NUM; private int n; private int w; int h; int l;/*算法實(shí)現(xiàn)* public void solve() int k = 1; int a = 1; for (int i = 1; i = n; i+) for (int j = 1; j = w; j+) a = 1; k = 1; if (weighti = j) h = weighti; l = valuei; while (h mi - 1j - h + l | mij (mi - 1j - h + l) /判斷是否應(yīng)該裝入 if (k = 1) /第一次的時(shí)候才執(zhí)行不放入的操作,k不等于1的時(shí)候保持上一次操作的結(jié)果不進(jìn)行改變 mij = mi - 1j;/不裝入 sij = 0; a = 0; else mij = mi - 1j - h + l;/應(yīng)該裝入 sij = k;/存放裝入次數(shù),用于求最優(yōu)解 k+;/裝入后k加1 h = weighti * k; l = valuei * k;/ System.out.println(h + e);/測試 / System.out.println(h + c);/ System.out.println(i + + j + + mij);/測試 else if (mij mi - 1j) /無法裝入 mij = mi - 1j; if (k = 1) sij = 0; / System.out.println(i + + j + + mij);/測試 System.out.println(可裝入物品的最大價(jià)值為: + mnw);/ for (int i = 1; i = n; i+) /測試/ for (int j = 1; j 1; i-) /由最后一個(gè)數(shù)據(jù)向上推算 y = y - xi * weighti; xi - 1 = si - 1y;/將每個(gè)物品的裝入信息存放起來 for (int i = 1; i = n; i+) System.out.println(第 + i + 個(gè)物品放入 + xi + 樣); public void input() Scanner scanner = new Scanner(System.in); System.out.println(請輸入背包能夠承受的總重量:); w = scanner.nextInt(); System.out.println(請輸入可以裝入背包的物品的種類:); n = scanner.nextInt(); System.out.println(請輸入 + n + 種物品中每一種物品的重量和價(jià)值:); for (int i = 1; i = n; i+) weighti = scanner.nextInt(); valuei = scanner.nextInt(); Test.javapackage chap4;/* * * author Jinyu */public class Test /* * param args the command line arguments */ public static void main(String args) / MatrixChainAp
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 志愿管理站管理制度
- 快遞站安全管理制度
- 總公司采購管理制度
- 意大利環(huán)境管理制度
- 成品鋁型材管理制度
- 戰(zhàn)隊(duì)群規(guī)范管理制度
- 房地產(chǎn)直銷管理制度
- 攝影部器材管理制度
- 收據(jù)與發(fā)票管理制度
- 教師五認(rèn)真管理制度
- 2024年小區(qū)地下車位租賃合同
- 2024年廣東省中考化學(xué)真題
- 期末監(jiān)測 試題 2023-2024學(xué)年教科版科學(xué)六年級下冊
- 光伏系統(tǒng)在智能溫室大棚中的設(shè)計(jì)與應(yīng)用
- 2024年新疆中考數(shù)學(xué)真題試卷及答案
- 2024深圳職業(yè)技術(shù)學(xué)院教師招聘考試筆試試題
- 美術(shù)家眼中的自己自畫像中的自我表現(xiàn)教案
- 個(gè)人裝修安全免責(zé)的協(xié)議書范本
- 化學(xué)與人類社會(huì)智慧樹知到期末考試答案章節(jié)答案2024年內(nèi)江師范學(xué)院
- GJB9001C-2017標(biāo)準(zhǔn)內(nèi)部宣貫培訓(xùn)
- 專業(yè)市場物業(yè)多種經(jīng)營管理規(guī)定
評論
0/150
提交評論