• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C#动态规划解决0-1背包问题

OC/C/C++ 水墨上仙 1580次浏览

C#动态规划解决0-1背包问题转自:http://blog.csdn.net/smart819819/article/details/8694272

// 利用动态规划解决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]];
            //  }
        }
    }
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C#动态规划解决0-1背包问题
喜欢 (0)
加载中……