贪心算法基础

  1 /*有一个背包，背包容量是M=150kg。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
  2 
  3 物品 A B C D E F G
  4 
  5 重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
  6 
  7 价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
  8 
  9 分析：
 10 
 11 目标函数：∑pi最大
 12 
 13 约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
 14 
 15 ⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
 16 
 17 ⑵每次挑选所占重量最小的物品装入是否能得到最优解？
 18 
 19 ⑶每次选取单位重量价值最大的物品，成为解本题的策略。
 20 */
 21 
 22 using System;
 23 using System.Collections.Generic;
 24 using System.Linq; 
 25 
 26 namespace GreedyAlgorithm
 27 {
 28     class Program
 29     {
 30         static void Main(string[] args)
 31         {
 32             Thing t1 = new Thing(10,35) { kg = 35, pirce = 10 }; 
 33             Thing t2 = new Thing(40,30) { kg = 30, pirce = 40 }; 
 34             Thing t3 = new Thing(30,6)  { kg =  6, pirce = 30 }; 
 35             Thing t4 = new Thing(50,50) { kg = 50, pirce = 50 }; 
 36             Thing t5 = new Thing(35,40) { kg = 40, pirce = 35 }; 
 37             Thing t6 = new Thing(40,10) { kg = 10, pirce = 40 }; 
 38             Thing t7 = new Thing(30,25) { kg = 25, pirce = 30 }; 
 39             List<Thing> list = new List<Thing>();
 40             list.Add(t1);
 41             list.Add(t2);
 42             list.Add(t3);
 43             list.Add(t4);
 44             list.Add(t5);
 45             list.Add(t6);
 46             list.Add(t7);
 47             //取重量最小的
 48             int b = 0;
 49             int forprice= getMAXKG(list ,out b);
 50             Console.WriteLine("取重量最小的--------------------重量:" + b + "    * *价格"+ forprice);
 51             Console.WriteLine("**********************************************************************");
 52             //取价值最高的
 53             int c = 0;
 54             int forp = getMAXPrice(list,out c);
 55             Console.WriteLine("取价格最大的--------------------重量:" + c + "    * *价格" + forp);
 56             Console.WriteLine("**********************************************************************");
 57             //取单价最高的 
 58             int d = 0;
 59             int univalence = getMAXunivalence(list, out d);
 60             Console.WriteLine("取价格最大的--------------------重量:" + d + "    * *价格" + univalence);
 61             Console.ReadKey();
 62         }
 63 
 64         private static int getMAXunivalence(List<Thing> li,out int b)
 65         {
 66             int a = 0;
 67             b = 0;
 68             List<Thing> c = li.OrderBy(i => i.univalence).ToList();
 69             foreach (var item in c)
 70             {
 71                 if (b + item.kg > 150)
 72                 {
 73                     return a;
 74                 }
 75                 a += item.pirce;
 76                 b += item.kg;
 77                 Console.WriteLine("按单价最小取--------------------：KG:" + item.kg.ToString() + "*       *Price:" + item.pirce.ToString() + "*  *单价" + item.univalence.ToString());
 78             }
 79             return a;
 80         }
 81 
 82         private static int getMAXPrice(List<Thing> li,out int  b)
 83         {
 84             int a = 0;
 85             b = 0;
 86             List<Thing> c = li.OrderByDescending(i => i.pirce).ToList();
 87             foreach (var item in c)
 88             {
 89                 if (b + item.kg > 150)
 90                 {
 91                     return a;
 92                 }
 93                 a += item.pirce;
 94                 b += item.kg;
 95                 Console.WriteLine("按价格最大取--------------------：kg:" + item.kg.ToString() + "*       *Price:" + item.pirce.ToString() + "*  *单价" + item.univalence.ToString());
 96             }
 97             return a;
 98         }
 99 
100         private static int getMAXKG(List<Thing> li,out int b) 
101         {
102             int a = 0;
103             b = 0; 
104             List<Thing> c=  li.OrderBy(i => i.kg).ToList();
105             foreach (var item in c)
106             {
107                 if (b + item.kg > 150)
108                 {
109                     return a;
110                 }
111                 a += item.pirce;
112                 b += item.kg;
113                 Console.WriteLine("按重量最小取--------------------：KG:" + item.kg.ToString() + "*       *Price:" +item.pirce.ToString()+"*  *单价"+ item.univalence.ToString());
114             }
115             return a;
116         }
117     }
118     public class Thing
119     {
120         public int kg  { get; set; } 
121         public int pirce { get; set; }
122         public float univalence;
123         public Thing(int a,int b)
124         {
125             univalence= (float)a / b;
126         }
127     }
128 }