青岛科技大学算法设计与分析实验报告-算法实训-背包问题

班级 学号 姓名 指导教师 庞志永

课程设计项目名称：背包问题的多项式时间近似方案

1.问题描述：

背包问题可描述为如下的整数规划形式，其中M为背包的容量，P为物体的价值，W为物体的体积。

maxnPx i1ii xi{0,1}, 1inn i1WixiM

2.基本要求：

(1)在给定参数K的条件下，设计背包问题的满足近似性能比不大于1+1/(k+1)的多项式时间近似方案，并选择适当的编程语言在计算机上实现。 (2)程序能够正常运行，计算结果正确，满足设计要求。

3.算法描述：

将装入背包的物体进行多次尝试，其方法是：

取K为确定的非负整数，考虑背包问题的实例I中的n个物体的合的K元素子集C，|C|=K。 (1)尝试将每个K元素子集C中的物体优先装入背包；

(2)利用解答背包问题的贪心算法A将(n-K)个物体尝试装入背包。合并先装入的K个物体和用算法A装入的剩余物体作为算法的最终解。 过程如下：

Procedure -APPROX(P,W,M,n,K) (1) PMAX=0;

(2) For all combinations C of size=K & weight≤M do (3) PC=i∈C Pi

(4) PMAX=max{PMAX,PC + L(I, P, W, M, n)}; (5) End for

(6) End -APPROX

Procedure L(I,P,W,M,n) (1) S1=0; T=M － i∈C Wi; (2) For i=1 to n do

(3) If i C and Wi≤T then (4) S1=S1+Pi, T=T – Wi (5) End if (6) End for

(7) S=max{S1,max{Pi| i C}}; (8) Return (S) (9) End L

4.模块划分(仅供参考)：

(1)输入及存储原始数据模块 (2)-APPROX(P,W,M,n,K)模块 (3)L(I,P,W,M,n)模块 (4)存储及输出结果模块

5.本课程设计中遇到的关键问题及其解决方法：

背包使用面向对象方法：

package knapsack;

public class Knapsack {

/** 背包重量 */ private int weight;

/** 背包物品价值 */ private int value; /*** * 构造器

*/

public Knapsack(int weight, int value) { this.value = value; this.weight = weight; }

public int getWeight() { return weight; }

public int getValue() { return value; }

public String toString() {

return \"[weight: \" + weight + \"\\" + \"value: \" + value + \"]\"; } }

获取最优解：

package knapsack;

import java.util.ArrayList; import java.util.List;

import javax.swing.JOptionPane;

import algorithm.dynamicplan.Knapsack; /** * 背包

* 首先将最多 k件物 品放人背包 ，

* 如果 这k件物品重量大于 c， 则放弃它。

* 否则， 剩余的重量用来考虑将剩余物品按价值重量比递减的顺序装入 。 * 通过考虑最多为 k件物品的所有可能的子集来得到最优解 。 *

* @author * */

public class KSMethod {

/**

* 输入及存储原始数据模块

* @param n * @return P */

static List InputData(int n){

String weight = JOptionPane.showInputDialog(\"Input

W(空格隔开):\");

String value = JOptionPane.showInputDialog(\"Input P(空

格隔开):\");

String[] values = value.split(\" \"); String[] weights = weight.split(\" \");

List P = new ArrayList(); for (int i = 0; i < n; i++) {

P.add(new Knapsack(Integer.valueOf(weights[i]), Integer

.valueOf(values[i]))); }

System.out.println(\"原始数据：\");

printlist(P); return P; } /**

* e-APPROX(P,W,M,n,K)模块 *

* @param bags1 * @param M * @param n * @param K * @return 解

*/

static int Solve(Knapsack[] bags1, int M, int n, int K) {

List> allSubLists = getSubLists(bags1);

List P = new ArrayList(); for (Knapsack knapsack : bags1) { P.add(knapsack); }

int Pmax = 0;

for (List I : allSubLists) {

int weight = 0;

for (Knapsack knapsack : I) {

weight = weight + knapsack.getWeight();

}

if ((I.size() <= K) && weight <= M) { int Pi = 0;

for (Knapsack knapsack : P) { // i++;

if (I.contains(knapsack)) {

Pi = Pi + knapsack.getValue(); }

}

Pmax = max(Pmax, Pi + L(I, P, M, n));

}

}// end for return Pmax; } /**

* L(I,P,W,M,n)模块

*

* @param I * @param P * @param M * @param n * @return */

static int L(List I, List P, int M, int n) {

int S = 0, S1 = 0; int SumWi = 0;

for (Knapsack knapsack : I) {

SumWi = SumWi + knapsack.getWeight(); }

int T = M - SumWi;

for (Knapsack knapsack : P) {

int Wi = knapsack.getWeight(); int Pi = knapsack.getValue();

if ((!I.contains(knapsack)) && Wi <= T) { S1 = S1 + Pi;

T = T - Wi; }

}

int[] t = max(P, I); if (t[1] + SumWi < M) { S = max(S1, t[0]);

}

return S; } /** * 遍历集合

*

* @param list */

static void printlist(List list) { for (Knapsack knapsack : list) { System.out.println(knapsack); }

} /** * 最大值

*

* @param a * @param b * @return max */

static int max(int a, int b) { return a > b ? a : b; } /**

* 计算max{Pi|i不属于I} *

* @param P * @param I * @return max */

static int[] max(List P, List I) {

int max = 0; int w = 0;

for (Knapsack knapsack : P) { if (I.contains(knapsack)) { continue; }

int temp = knapsack.getValue(); if (max > temp) { max = temp;

w = knapsack.getWeight(); } }

return new int[] { max, w }; } /**

* 得到所有子集

*

* @param array * @return */ static List> getSubLists(Knapsack[] array) {

List> allsubLists = new ArrayList>();

int max = 1 << array.length; for (int i = 0; i < max; i++) { List subList = new ArrayList(); int k = i;

int index = 0; while (k > 0) {

if ((k & 1) > 0) {

subList.add(array[index]); }

k >>= 1;

}

}

index++; }

allsubLists.add(subList); }

return allsubLists;

程序入口：

package knapsack;

import java.util.ArrayList; import java.util.List;

import javax.swing.JOptionPane;

import algorithm.dynamicplan.Knapsack;

public class K7_4 {

public static void main(String[] args) {

int n =

Integer.valueOf(JOptionPane.showInputDialog(\"Input N:\")); int m =

Integer.valueOf(JOptionPane.showInputDialog(\"Input M:\"));

System.out.println(\"背包容量：\"+m);

List P=new ArrayList(); P = KSMethod.InputData(n); int k =

Integer.valueOf(JOptionPane.showInputDialog(\"Input K:\")); Knapsack[] bags = P.toArray(new Knapsack[0]); String res = null;

for (int i = 0; i < k; i++) {

res= \"最优解(价值总和)：\"+KSMethod.Solve(bags, m, n,

i);

System.out.println(\"当k=\"+i+\":\"+res);

} } }

6.运行结果及其相关描述：

要求实例中物体的数量在20—100之间。

背包容量：50 原始数据：

[weight: 1 value: 5] [weight: 2 value: 5] [weight: 3 value: 5] [weight: 4 value: 5] [weight: 5 value: 5] [weight: 6 value: 7] [weight: 7 value: 7] [weight: 8 value: 8] [weight: 9 value: 9] [weight: 10 value: 10] [weight: 11 value: 11] [weight: 12 value: 12] [weight: 13 value: 13] [weight: 14 value: 14] [weight: 15 value: 15] [weight: 16 value: 16] [weight: 17 value: 17] [weight: 18 value: 18] [weight: 19 value: 19] [weight: 20 value: 20] 当k=0:最优解(价值总和)：56 当k=1:最优解(价值总和)：61 当k=2:最优解(价值总和)：61 当k=3:最优解(价值总和)：61 当k=4:最优解(价值总和)：61 当k=5:最优解(价值总和)：61 当k=6:最优解(价值总和)：61 当k=7:最优解(价值总和)：61 当k=8:最优解(价值总和)：61 当k=9:最优解(价值总和)：61

7.课程设计总结：

通过这次实验，深刻体会到算法的无限魅力。