算法背包問題#課堂參考

1、實(shí)驗(yàn)題目：背包問題實(shí)驗(yàn)?zāi)康模赫莆談?dòng)態(tài)規(guī)劃、貪心算法的原理，并能夠按其原理編程實(shí)現(xiàn)解決背包問題，以加深對(duì)上述方法的理解。實(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)遞推方

2、程、邊界條件、標(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)目，并對(duì)其進(jìn)行保存； 3在新建的項(xiàng)目下對(duì)我們所分析的題目進(jìn)行編寫； 4、調(diào)試所編寫的程序； 5、運(yùn)行文件，并對(duì)其進(jìn)行測(cè)試，看是否正確。實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)小結(jié)：在做本次實(shí)驗(yàn)之前，自

3、己對(duì)動(dòng)態(tài)規(guī)劃、貪心算法的原理不是非常的理解，花了很多時(shí)間看了課本上的相關(guān)內(nèi)容。當(dāng)你懂得算法的基本原理后，再參考老師所提供的代碼進(jìn)行完善補(bǔ)充，必須結(jié)合算法的實(shí)際情況對(duì)代碼中的相關(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

4、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;

5、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

6、= 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);/測(cè)試 / System.out.println(h + c);/ System.out.println(i + + j + + mij);/測(cè)試 else if (mij mi - 1j) /無法裝入 mij = mi - 1j; if (k = 1) sij = 0; / System.out.println(i +

7、 + j + + mij);/測(cè)試 System.out.println(可裝入物品的最大價(jià)值為： + mnw);/ for (int i = 1; i = n; i+) /測(cè)試/ 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 Sca

8、nner(System.in); System.out.println(請(qǐng)輸入背包能夠承受的總重量：); w = scanner.nextInt(); System.out.println(請(qǐng)輸入可以裝入背包的物品的種類：); n = scanner.nextInt(); System.out.println(請(qǐng)輸入 + 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) /