// 利用動(dòng)態(tài)規(guī)劃解決0-1背包問題using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Knapsack_problem// 背包問題關(guān)鍵在于計(jì)算不超過背包的總?cè)萘康淖畲髢r(jià)值{ class Program {  static void Main()  {   int i;   int capacity = 16;   int[] size = new int[] { 3, 4, 7, 8, 9 };   // 5件物品每件大小分別為3, 4, 7, 8, 9    //且是不可分割的 0-1 背包問題   int[] values = new int[] { 4, 5, 10, 11, 13 };   // 5件物品每件的價(jià)值分別為4, 5, 10, 11, 13   int[] totval = new int[capacity + 1];   // 數(shù)組totval用來存貯最大的總價(jià)值   int[] best = new int[capacity + 1];   // best 存貯的是當(dāng)前價(jià)值最高的物品   int n = values.Length;   for (int j = 0; j <= n - 1; j++)    for (i = 0; i <= capacity; i++)     if (i >= size[j])      if (totval[i] < (totval[i - size[j]] + values[j]))   // 如果當(dāng)前的容量減去J的容量再加上J的價(jià)值比原來的價(jià)值大，   //就將這個(gè)值傳給當(dāng)前的值      {       totval[i] = totval[i - size[j]] + values[j];       best[i] = j; // 并把j傳給best      }   Console.WriteLine("背包的最大價(jià)值: " + totval[capacity]);   // Console.WriteLine("構(gòu)成背包的最大價(jià)值的物品是: " );   // int totcap = 0;   // while (totcap <= capacity)   // {   //  Console.WriteLine("物品的大小是：" + size[best[capacity - totcap]]);   //  for (i = 0; i <= n-1; i++)   //  totcap += size[best[i]];   // }  } }}