本文共 7672 字，大约阅读时间需要 25 分钟。
基本步骤：
1、算每种物品单位重量的价值Vi/Wi
2、依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包
3、若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包
4、依此策略一直地进行下去，直到背包装满为止
package cn.edu.xmu.acm.greedy;import java.util.Arrays;import java.util.Scanner;/** * desc:贪心策略求解背包问题 * KnapSackGreedy * @author chenwq (irwenqiang@gmail.com) * @version 1.0 2012/03/27 */public class KnapSackGreedy{ public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("Please enter the number of objects:"); int n = in.nextInt(); int[] w = new int[n]; int[] v = new int[n]; System.out .println("Now,please enter the weight of these objects:"); for (int i = 0; i < n; i++) { w[i] = in.nextInt(); } System.out .println("Now,please enter the value of these objects:"); for (int i = 0; i < n; i++) { v[i] = in.nextInt(); } System.out .println("Now,please enter the capacity of the pack:"); int c = in.nextInt(); /** * 1、计算单位价值 * 2、按单位重量价值 r[i]=v[i]/w[i]降序排列 */ double startTime = System.currentTimeMillis(); double[] r = new double[n]; int[] index = new int[n]; for (int i = 0; i < n; i++) { r[i] = (double) v[i] / (double) w[i]; index[i] = i; } double temp = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (r[i] < r[j]) { temp = r[i]; r[i] = r[j]; r[j] = temp; int x = index[i]; index[i] = index[j]; index[j] = x; } } } /** * 排序后的重量和价值分别存到w1[]和v1[]中 */ int[] w1 = new int[n]; int[] v1 = new int[n]; for (int i = 0; i < n; i++) { w1[i] = w[index[i]]; v1[i] = v[index[i]]; } /** * 打印按单位价值降序之后的物品和物品价值序列 */ System.out.println(Arrays.toString(w1)); System.out.println(Arrays.toString(v1)); /** * 初始化解向量x[n] */ int[] x = new int[n]; for (int i = 0; i < n; i++) { x[i] = 0; } /** * 按照贪心策略求解并打印解向量 */ for (int i = 0; i < n; i++) { if (w1[i] < c) { x[i] = 1; c = c - w1[i]; } } System.out .println("The solution vector is:" + Arrays.toString(x)); /** * 根据解向量求出背包中存放物品的最大价值并打印 */ int maxValue = 0; for (int i = 0; i < n; i++) { if (x[i] == 1) maxValue += v1[i]; } double endTime = System.currentTimeMillis(); System.out .println("Now,the largest values of objects in the pack is:" + maxValue); System.out.println("Basic Statements take) " + (endTime - startTime) + " milliseconds!"); }} 背包问题拓展:物品可以部分放入背包中。详细见下述代码
package cn.edu.xmu.acm.greedy;import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.InputStreamReader;import java.text.DecimalFormat;/* * Basic knapsack problem: * * We are given n objects and a knapsack. Each object has a positive * weight and a positive value. The knapsack is limited in the weight * that it can carry. Fill the knapsack in a way that maximizes the * value of the included objects, where you are allowed to take a * fraction of an object. * * Author: Timothy Rolfe * * Based on Brassard and Bratley, _Fundamentals_of_Algorithmics_, * pp. 202-04. * * Note: The array "avail" is sorted several times, each with a * different criterion for sorting. Only the last time is * the optimal knapsack obtained (when sorted by value per weight). */public class FPKnapsack { // Instance-scope fields int n; // Number of objects Item[] avail;// Available objects for use Item[] used; // objects actually used int nUsed; double maxWeight; // Weight limit of the knapsack. // Easy-out for IOExceptions --- throw them back to the operating system public static void main(String[] args) throws Exception { // Code for reading console from "Java in a Nutshell", p. 166 BufferedReader console = new BufferedReader(new InputStreamReader( System.in)); FPKnapsack knap = new FPKnapsack(); String lineIn; String[] header = { "ranked by increasing weight", "ranked by decreasing value", "ranked by decreasing value per weight" }; int k; // Loop variable System.out.print("Input file name: "); if (args.length < 1) lineIn = console.readLine(); else { lineIn = args[0]; System.out.println(args[0]); } File f = new File(lineIn); FileReader fis = new FileReader(f); BufferedReader inp = new BufferedReader(fis); knap.initialize(inp); for (k = 0; k < 3; k++) { knap.fill(k); knap.report(header[k]); } } /* * Data file presumption: * * 1. Weight ceiling for the knapsack (one number on the line) 2. Number of * candidate objects (one number on the line) ...That many number PAIRS: * weight value */ void initialize(BufferedReader inp) throws Exception { String lineIn; lineIn = inp.readLine(); maxWeight = Double.parseDouble(lineIn.trim()); lineIn = inp.readLine(); n = Integer.parseInt(lineIn.trim()); // Arrays "used" and "avail" are initialized here. used = new Item[n]; avail = new Item[n]; System.out.println("\nData accepted: n = " + n); System.out.println("Individual object descriptions follow."); for (int k = 0; k < n; k++) { DecimalFormat fmt0 = new DecimalFormat("0"), fmt2 = new DecimalFormat( "0.00"); java.util.StringTokenizer tk = new java.util.StringTokenizer( inp.readLine()); double wt = Double.parseDouble(tk.nextToken()), val = Double .parseDouble(tk.nextToken()); avail[k] = new Item(wt, val); System.out.println("w: " + fmt0.format(wt) + " v: " + fmt0.format(val) + " v/w: " + fmt2.format(val / wt)); } } // Fill the knapsack (i.e., move items from the heap into used[]) void fill(int basis) { int k; Item nxt; double remain = maxWeight; nUsed = 0; // Put the available items into requested order Item.setBasis(basis); java.util.Arrays.sort(avail); for (k = 0; remain > 0 && k < avail.length; k++) { nxt = avail[k]; if (nxt.w <= remain) nxt.x = 1; else nxt.x = remain / nxt.w; remain -= nxt.x * nxt.w; used[nUsed++] = nxt; } } // Show the contents --- as number pairs and fraction used. void report(String header) { DecimalFormat fmt0 = new DecimalFormat("0"), fmt2 = new DecimalFormat( "0.00"); double sigVal = 0; System.out.println("\n" + fmt0.format(maxWeight) + " total weight " + header); System.out.println("Knapsack contents:"); for (int k = 0; k < nUsed; k++) { String lineOut = "("; lineOut += fmt0.format(used[k].w) + ", "; lineOut += fmt0.format(used[k].v) + ") --- "; lineOut += fmt2.format(used[k].x) + " used."; System.out.println(lineOut); sigVal += used[k].v * used[k].x; } System.out.println("Total value: " + fmt2.format(sigVal)); }}/* * Class of items for inclusion in the knapsack */class Item implements Comparable { double w, // For each object, the weight of the object v, // For each object, the value of the object x; // For each object, the fraction of the object used double vpw; // For each object, the value-per-weight ratio // Basis for sorting: 0: w ascending, // 1: v descending // x: vpw descending static private int basis = 2; Item(double w, double v) { this.x = 0; this.w = w; this.v = v; this.vpw = v / w; } Item(Item c) { this.w = c.w; this.w = c.w; this.v = c.v; this.vpw = c.vpw; } public static void setBasis(int basis) { Item.basis = basis; } // Comparable insists on the following method signature: public int compareTo(Object x) { Item rt = (Item) x; // Basis for ordering is set in the static field basis switch (basis) { // ascending case 0: return w < rt.w ? -1 : w > rt.w ? +1 : 0; // descending case 1: return v < rt.v ? +1 : v > rt.v ? -1 : 0; // descending default: return vpw < rt.vpw ? +1 : vpw > rt.vpw ? -1 : 0; } }} ref:http://penguin.ewu.edu/cscd320/Topic/Strategies/Knapsack.html#fill_method
转载地址：http://svwob.baihongyu.com/