完全背包問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)題目：完全背包問題實(shí)驗(yàn)?zāi)康模簩W(xué)習(xí)掌握動(dòng)態(tài)規(guī)劃算法學(xué)習(xí)劃分子問題及確定優(yōu)化函數(shù)并 掌握其思想實(shí)驗(yàn)內(nèi)容： 一個(gè)旅行者準(zhǔn)備隨身攜帶一個(gè)背包. 可以放入背包的物品有n 種, 每種物品的重量和價(jià)值分別為 wj , vj . 如果背包的最大重量限制是 b, 怎樣選擇放入背包的物品以使得背包的價(jià)值最大?實(shí)驗(yàn)步驟：由線性條件約束的線性函數(shù)取最大或最小的問題Fk(y)：裝前 k 種物品, 總重不超過 y, 背包的最大價(jià)值ik(y)：裝前 k 種物品, 總重不超過 y, 背包達(dá)最大價(jià)值時(shí)裝入物品的最大標(biāo)號(hào)確定遞推方程、邊界條件、標(biāo)記函數(shù)實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)代碼：package packsa

2、ck;import java.util.Scanner;public class Project static final int MAX_NUM = 20; static final int MAX_WEIGHT = 100; 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

3、 s = new intMAX_NUMMAX_NUM; private int n; private int w; public void solve() for (int i = 1; i <= n; i+) for (int j = 1; j <= w; j+) if (weighti <= j) if (mi - 1j > mij - weighti + valuei) mij = mi - 1j; sij = si-1j; else mij = mi j - weighti + valuei; sij = i; else mij = mi - 1j; sij =

4、 si-1j; System.out.println("可裝入物品的最大價(jià)值為：" + mnw); public void trackSolution() int y=w; int j = n; while(y!=0) j = sjy; xj = 1; y = y - weightj; while(sjy = j) y = y - weightj; xj+; System.out.print( "最佳裝入方案："); for (int i=1;i<=n;i+) System.out.print(xi); if(i!=n) System.out.pr

5、int(","); System.out.println( ""); public void input() Scanner scanner = new Scanner(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+) valuei = scanner.nextInt(); System.out.println("請(qǐng)輸入" + n + "種物品中每一種物品的重量："); for (int i = 1; i <= n; i+) weighti = scanner.nextInt(); package packsack;public class Test public static void main(St