动态规划：背包问题

 1         /// <summary>
 2         /// 动态规划：背包问题
 3         /// </summary>
 4         private static void MaxVal()
 5         {
 6             int capacity = 16;  //背包负重
 7             int[] size = new int[] { 3,4,7,8,9 };       //物品大小    
 8             int[] values = new int[] { 4,5,10,11,13 };  //物品价值
 9             int[] totval = new int[capacity + 1];   //可负载物品的价值总量
10             int[] best = new int[capacity + 1];     //可负载物品的价值的下标
11             int n = values.Length;
12             for (int j = 0; j <= n - 1; j++)
13             {
14                 for (int i = 0; i <= capacity; i++)
15                 {
16                     if (i >= size[j])   //背包重量大于任何一个物品的重量
17                     {
18                         if (totval[i] < (totval[i - size[j]] + values[j]))
19                         {
20                             totval[i] = totval[i - size[j]] + values[j];                          
21                             best[i] = j;
22                         }
23                     }
24                 }
25             }
26             Console.WriteLine(totval[capacity]);       
27         }
工欲善其事，必先利其器。