背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1 <= i <= n。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
基本步骤：
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
Knap.rar (118 Bytes)
下载次数: 4
0
顶
0
踩
分享到：
2012-03-27 21:27
浏览 5458
评论