班级 学号 姓名 指导教师 庞志永
课程设计项目名称:背包问题的多项式时间近似方案
1.问题描述:
背包问题可描述为如下的整数规划形式,其中M为背包的容量,P为物体的价值,W为物体的体积。
maxnPx i1ii xi{0,1}, 1inn i1WixiM
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 String weight = JOptionPane.showInputDialog(\"Input W(空格隔开):\"); String value = JOptionPane.showInputDialog(\"Input P(空 格隔开):\"); String[] values = value.split(\" \"); String[] weights = weight.split(\" \"); List 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 List int Pmax = 0; for (List 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 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 } /** * 最大值 * * @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 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 List int max = 1 << array.length; for (int i = 0; i < max; i++) { List 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 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.课程设计总结: 通过这次实验,深刻体会到算法的无限魅力。 因篇幅问题不能全部显示,请点此查看更多更全内容> allSubLists = getSubLists(bags1);
> getSubLists(Knapsack[] array) {
> allsubLists = new ArrayList
>();
Copyright © 2019- oldu.cn 版权所有 浙ICP备2024123271号-1
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务