完全背包问题

1、实验题目：完全背包问题实验目的：1、 学习掌握动态规划算法2、 学习划分子问题及确定优化函数并 掌握其思想实验内容： 一个旅行者准备随身携带一个背包. 可以放入背包的物品有n 种, 每种物品的重量和价值分别为 wj , vj . 如果背包的最大重量限制是 b, 怎样选择放入背包的物品以使得背包的价值最大?实验步骤：1、 由线性条件约束的线性函数取最大或最小的问题2、 Fk(y)：装前 k 种物品, 总重不超过 y, 背包的最大价值3、 ik(y)：装前 k 种物品, 总重不超过 y, 背包达最大价值时装入物品的最大标号4、 确定递推方程、边界条件、标记函数实验结果：实验代码：package p

2、acksack;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 fina

3、l int 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 mij - weighti + valuei) mij = mi - 1j; sij = si-1j; else mij = mi j - weighti + valuei; sij = i; else mij = mi - 1j; sij = si-1j; System.out.println(可装

4、入物品的最大价值为： + 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.print(,); System.out.println( ); public void input() Scanne

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