完全背包問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗題目：完全背包問題實驗?zāi)康模簩W習掌握動態(tài)規(guī)劃算法學習劃分子問題及確定優(yōu)化函數(shù)并 掌握其思想實驗內(nèi)容： 一個旅行者準備隨身攜帶一個背包. 可以放入背包的物品有n 種, 每種物品的重量和價值分別為 wj , vj . 如果背包的最大重量限制是 b, 怎樣選擇放入背包的物品以使得背包的價值最大?實驗步驟：由線性條件約束的線性函數(shù)取最大或最小的問題Fk(y)：裝前 k 種物品, 總重不超過 y, 背包的最大價值ik(y)：裝前 k 種物品, 總重不超過 y, 背包達最大價值時裝入物品的最大標號確定遞推方程、邊界條件、標記函數(shù)實驗結(jié)果：實驗代碼：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("可裝入物品的最大價值為：" + 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("請輸入背包能夠承受的總重量："); w = scanner.nextInt(); System.out.println("請輸入可以裝入背包的物品的種類："); n = scanner.nextInt(); System.out.println("請輸入" + n + "種物品中每一種物品的價值："); for (int i = 1; i <= n; i+) valuei = scanner.nextInt(); System.out.println("請輸入" + n + "種物品中每一種物品的重量："); for (int i = 1; i <= n; i+) weighti = scanner.nextInt(); package packsack;public class Test public static void main(St