- // 利用动态规划解决0-1背包问题
- 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]];
- // }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/080820135043.html
来源: http://www.codesnippet.cn/detail/080820135043.html