using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

 

namespace Knapsack_problem  // 背包问题关键在于计算不超过背包的总容量的最大价值

    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件物品每件的价值分别为4, 5, 10, 11, 13

            int[] totval = new int[capacity + 1];  // 数组totval用来存贮最大的总价值

            int[] best = new int[capacity + 1];    // best 存贮的是当前价值最高的物品

            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])) // 如果当前的容量减去J的容量再加上J的价值比原来的价值大，就将这个值传给当前的值

                        {

                            totval[i] = totval[i - size[j]] + values[j];

                            best[i] = j;                                  // 并把j传给best

                        }

            Console.WriteLine("背包的最大价值: " + totval[capacity]);

            //   Console.WriteLine("构成背包的最大价值的物品是: " );

            //    int totcap = 0;

 

 

            //  while (totcap <= capacity)

            //   {

            //     Console.WriteLine("物品的大小是：" + size[best[capacity - totcap]]);

            //     for (i = 0; i <= n-1; i++)

            //     totcap += size[best[i]];

            //  }

 

 

        }

    }