贪心算法 - 三种贪心选择策略 - 求解0-1背包问题

贪心算法能解决背包问题,但是不能解决0-1背包问题.

用算法问解0-1背包问题时,其解不一定是最优解,得到的可能是近似最优解.

根据选择的贪心策略选择的不同,得到的近似最优解也不尽相同.

 

/*
@author jarg
@TODO 贪心算法 - 求解0-1背包问题
贪心策略: 1. 单价 2. 重量 3. 单位价值
*/

import java.util.*;

public class Knapsack
{
	public static int m = 10;						// 背包容量
	public static int n = 4;						// 物品个数
	public static int[] w = {7, 3, 4, 5};			// 物品重量
	public static int[] v = {12, 12, 40, 25};		// 物品单价

	/* 排序结果 */
	public static int[] sort = new int[n];
	public static int[] choice = new int[n];

	public static void main(String[] args)
	{
		greedyByValue();
		greedyByWeight();
		greedyByPrice();
		System.out.println("");
	}

	/* 单价贪心策略 type:0 */
	public static void greedyByValue()
	{
		System.out.println("-单价贪心策略:");
		choice(0);
	}

	/* 重量贪心策略 type:1 */
	public static void greedyByWeight()
	{
		System.out.println("-重量贪心策略:");
		choice(1);
	}

	/* 单位价值贪心策略 type:2 */
	public static void greedyByPrice()
	{
		System.out.println("-单位价值贪心策略:");
		choice(2);
	}

	public static void choice(int type)
	{
		sort(type);
		//display(choice);

		int tempW = 0;
		for(int i=0;i<n;i++)
		{
			tempW = tempW + w[choice[i]];
			if(tempW<m)
			{
				sort[i] = choice[i];
			}
			else
			{
				sort[i] = -1;
			}
		}
		display(sort);
		
	}

	/* 排序 */
	public static void sort(int type)
	{
		int[] temp = getTempData(type);
		
		for(int i=0;i<n;i++)
		{
			choice[i] = i;
		}

		for(int i=0;i<n-1;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				if(temp[j]>temp[i])
				{
					int t = choice[j];
					choice[j] = choice[i];
					choice[i] = t;

					t = temp[j];
					temp[j] = temp[i];
					temp[i] = t;
				}
			}
		}
		
	}

	public static int[] getTempData(int type)
	{
		/* 待排序的数据 */
		int[] temp = new int[n];
		if(type == 0)
		{
			temp = v;
		}
		else if(type == 1)
		{
			temp = w;
		}
		else
		{
			for(int i=0;i<n;i++)
			{
				temp[i] = v[i]/w[i];
			}
		}
		return temp;
	}

	public static void display(int[] value)
	{
		int sumv = 0;
		System.out.print("choice: ");
		for(int i=0;i<n;i++)
		{
			if(sort[i] == -1)
			{
				break;
			}
			sumv = sumv + v[sort[i]] * w[sort[i]];
			System.out.print(sort[i] + "\t");
		}
		System.out.println();
		for(int i=0;i<n;i++)
		{
			if(sort[i] == -1)
			{
				break;
			}
			System.out.println("w[" + sort[i] + "]: " + w[sort[i]] + "\tv[" + sort[i] + "]: " + v[sort[i]]);
		}
		System.out.println("总价值: " + sumv + "\n");
	}
}

 

 

今天浑浑噩噩度过了一下,看贪心算法求解0-1背包问题,不知道思考.

试着写程序,做一半就做不下去.耗了很久.

最终还是决定坚持代码完整性,即使这个程序写得很滥.