背包问题 * 贪心准则：价值密度贪心

代码

package LQB14;

import java.util.Scanner;


public class T9 {

		public static float C1 = 0;// 总价值

		public static void main(String[] args) {
			// TODO Auto-generated method stub
			Scanner scanner = new Scanner(System.in);
			System.out.print("请输入物品的个数：");
			int n = scanner.nextInt();
			System.out.print("请输入背包的容量：");
			float C = scanner.nextFloat();
			System.out.println("请输入物品的重量和价值：");
			float[] wi = new float[n + 2];
			float[] vi = new float[n + 2];
			float[] x = new float[n + 2];
			float[] v2 = new float[n + 1];
			float[] w2 = new float[n + 1];
			for (int i = 1; i <= n; i++) {
				wi[i] = scanner.nextFloat();
				vi[i] = scanner.nextFloat();
				v2[i] = vi[i];
				w2[i] = wi[i];
			}
			T9 test = new T9();
			test.Knapsack(n, C, vi, wi, x, v2, w2);
			System.out.println();
			System.out.print("单个物品价值：");
			for (int i = 1; i <= n; i++) {
				System.out.print("t" + v2[i]);
			}
			System.out.println();
			System.out.println("背包的总价值为：" + C1);
		}

		
		void Sort(int n, float[] v, float w[]) {
			float temp1;
			float temp2;
			for (int i = 1; i <= n; i++) {
				for (int s = 1; s <= i; s++) {
					if (v[i] / w[i] > v[s] / w[s]) {
						temp1 = v[s];
						temp2 = w[s];
						v[s] = v[i];
						w[s] = w[i];
						v[i] = temp1;
						w[i] = temp2;

					}
				}
			}
		}

		void Knapsack(int n, float W, float v[], float w[], float x[], float v2[], float w2[]) {
			T9 a = new T9();
			a.Sort(n, v, w);
			int i;
			for (i = 1; i <= n; i++)
				x[i] = 0;
			float c = 0;

			for (i = 1; i <= n; i++) {
				if (w[i] > W)
					break;// 如果物品的重量大于背包剩余容量，停止放入整个物品
				for (int t = 1; t <= n; t++) {
					if (w[i] == w2[t] && v[i] == v2[t])// 将放入了的物品标记为1
						x[t] = 1;
				}
				W -= w[i];
				c += v[i];
			}
			if (i <= n) {
				for (int q = 1; q <= n; q++) {
					if (w[i] == w2[q] && v[i] == v2[q]) {
						x[q] = W / w[i];// 放入部分物品记录放入的比例
						c += x[q] * v[i];
					}
				}

			}
			System.out.print("放入重量比例：");
			for (int k = 1; k <= n; k++) {
				System.out.print("t" + x[k]);
			}
			C1 = c;
		}
	
	}