getportionbag.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 122 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//13 Mar 2008
package cn.edu.whu.iss.algorithm.unit16;

import cn.edu.whu.iss.algorithm.unit07.QuickSort;

public class GetPortionBag {
	private PortionBagObj[] things;
	private int weightAll;
	private int priceAll;

	public GetPortionBag(PortionBagObj[] things, int weightAll) {
		super();
		this.things = things;
		this.weightAll = weightAll;
	}

	public PortionBagObj[] getThings() {
		return things;
	}

	public void setThings(PortionBagObj[] things) {
		this.things = things;
	}

	public int getWeightAll() {
		return weightAll;
	}

	public void setWeightAll(int weightAll) {
		this.weightAll = weightAll;
	}

	public int getRes() {
		return get();
	}

	private int get() {
		ThingProperty[] pro = new ThingProperty[things.length];
		for (int i = 0; i < pro.length; i++) {
			pro[i] = new ThingProperty(things[i]);
		}
		int p = 0;
		int r = pro.length - 1;
		while (p < r) {
			int q = QuickSort.randomizedPartition(pro, p, r);
			int tot = 0;
			priceAll = 0;
			for (int i = 0; i < q + 1; i++) {
				tot += pro[i].getWeight();
				priceAll += pro[i].getPrice();
			}
			if (tot == weightAll) {
				break;
			} else if (tot > weightAll) {
				r = q - 1;
			} else {
				if (q + 1 < pro.length) {
					priceAll += pro[q + 1].getValue()
							* Math.min((weightAll - tot), pro[q + 1]
									.getWeight());
				}
				p = q + 1;
			}
		}
		return priceAll;
	}

	private class ThingProperty implements Comparable<ThingProperty> {
		private PortionBagObj obj;
		private float value;

		public ThingProperty(PortionBagObj obj) {
			this.obj = obj;
			value = Float.intBitsToFloat(obj.getPrice())
					/ Float.intBitsToFloat(obj.getWeight());
		}

		public int compareTo(ThingProperty o) {
			if (this.value >= o.getValue()) {
				return -1;
			} else {
				return 1;
			}
		}

		public PortionBagObj getObj() {
			return obj;
		}

		public void setObj(PortionBagObj obj) {
			this.obj = obj;
		}

		public int getPrice() {
			return obj.getPrice();
		}

		public int getWeight() {
			return obj.getWeight();
		}

		public float getValue() {
			return value;
		}

		public void setValue(float value) {
			this.value = value;
		}

	}

}