C#使用动态规划解决0-1背包问题实例分析

本文实例讲述了C#使用动态规划解决0-1背包问题的方法。分享给大家供大家参考。具体如下：

// 利用动态规划解决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.背包问题介绍 背包问题不单单是一个简单的算法问题,它本质上代表了一大类问题,这类问题实际上是01线性规划问题,其约束条件和目标函数如下: 自从dd_engi在2007年推出<背包问题九讲>之后,背包问题的主要精髓基本已道尽.本文没有尝试对背包问题的本质进行扩展或深入挖掘,而只是从有限的理解(这里指对<背包问题九讲>的理解)出发,帮助读者更快地学习<背包问题九讲>中的提到的各种背包问题的主要算法思想,并通过实例解释了相应的算法,同时给出了几个背包问题的经典应用. 2.

  • C#用递归算法解决经典背包问题

    1.引子 我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,用脑子才行,下面就教您如何解决这样的问题,以获得更多的奖品. 2.应用场景 在一个物品向量中找到一个子集满足条件如下 : 1)这个子集加起来的体积大小不能大于指定阀值 2)这个物品子集加起来价值大小是向量V中所有满足条件1的子集中最大的 3.分析 背包问题有好多版本,本文只研究0/1版本,即对一个物体要么选用,要么就抛弃,不能将一个

  • PHP动态规划解决0-1背包问题实例分析

    本文实例分析了PHP动态规划解决0-1背包问题.分享给大家供大家参考.具体分析如下: 背包问题描述:一个承受最大重量为W的背包,现在有n个物品,每个物品重量为t, 每个物品的价值为v. 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大. 思路:定义一个二维数组,一维为物品数量(表示每个物品),二维是重量(不超过最大,这里是15),下面数组a, 动态规划原理思想,max(opt(i-1,w),wi+opt(i-1,w-wi)) 当中最大值, opt(i-1,w-wi)指上一个最优解

  • C++动态规划之背包问题解决方法

    本文实例讲述了C++动态规划之背包问题解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 背包的最大容量为W,有N件物品,每件物品重量为w,价值为p,怎样选择物品能使得背包里的物品价值最大? 输入: 10 3   (W,N) 4 5   (w,p) 6 7   (w,p) 8 9   (w,p) 实现代码: #include <stdio.h> #define THING 20 #define WEIGHT 100 int arr[THING][WEIGHT]; /* 背包容量为wei

  • C#使用回溯法解决背包问题实例分析

    本文实例讲述了C#使用回溯法解决背包问题的方法.分享给大家供大家参考.具体如下: 背包问题描述: 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高 实现代码: using System; using System.Collections.Generic; using System.Text; namespace BackRack { //要装入书包的货物节点 class BagNode { public int mark;//货物编号,从0开始

  • 用贪心法求解背包问题的解决方法

    贪心方法:总是对当前的问题作最好的选择,也就是局部寻优.最后得到整体最优.应用:1:该问题可以通过"局部寻优"逐步过渡到"整体最优",这是贪心选择性质与"动态规划"的主要差别.2:最优子结构性质:某个问题的整体最优解包含了"子"问题的最优解.完整的代码如下: 复制代码 代码如下: #include "iostream"using namespace std;struct goodinfo{ float p;

  • PHP回溯法解决0-1背包问题实例分析

    本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna

  • PHP贪婪算法解决0-1背包问题实例分析

    本文实例讲述了PHP贪婪算法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活! //0-1背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } }

  • C#使用动态规划解决0-1背包问题实例分析

    本文实例讲述了C#使用动态规划解决0-1背包问题的方法.分享给大家供大家参考.具体如下: // 利用动态规划解决0-1背包问题 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Knapsack_problem // 背包问题关键在于计算不超过背包的总容量的最大价值 { class Program { static void Main() { int i;

  • php解决约瑟夫环算法实例分析

    本文实例讲述了php解决约瑟夫环算法.分享给大家供大家参考,具体如下: 今天偶遇一道算法题 "约瑟夫环"是一个数学的应用问题:一群猴子排成一圈,按1,2,-,n依次编号.然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去-,如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王.要求编程模拟此过程,输入m.n, 输出最后那个大王的编号. 方法一:递归算法 function killMonkey($monkeys , $m , $cu

  • 通过jstack分析解决进程死锁问题实例代码

    刚才用jstack解决了一个进程死锁的问题--其实早就解决了,也知道原因,只是一直没找到死锁的位置,不太甘心而已. 流程大致如下: (0)环境要求,JDK1.6及以上 (1)先找到进程的PID,Windows下,打开进程管理器,按照名字排序,可以找到叫做javaw.exe的进程(java虚拟机进程一律叫做javaw.exe),要找出哪个是你的进程,记住当前进程列表,然后重启你的进程,PID刷新过的那个即是你的进程. (2)在CMD下运行:jstack pid,jstack会在console上打出

  • python web.py开发httpserver解决跨域问题实例解析

    使用web.py做http server开发时,遇到postman能够正常请求到数据,但是浏览器无法请求到数据,查原因之后发现是跨域请求的问题. 跨域请求,就是在浏览器窗口中,和某个服务端通过某个 "协议+域名+端口号" 建立了会话的前提下,去使用与这三个属性任意一个不同的源提交了请求,那么浏览器就认为你是跨域了,违反了浏览器的同源策略. w3c标准中,有针对跨域请求的规范,在响应头中有以下三种跨域访问限制: Access-Control-Allow-Origin:限制允许跨域访问的源

  • Java 分析并解决内存泄漏的实例

    这几天,一直在为Java的"内存泄露"问题纠结.Java应用程序占用的内存在不断的.有规律的上涨,最终超过了监控阈值.福尔摩 斯不得不出手了! 分析内存泄露的一般步骤 如果发现Java应用程序占用的内存出现了泄露的迹象,那么我们一般采用下面的步骤分析: 把Java应用程序使用的heap dump下来 使用Java heap分析工具,找出内存占用超出预期(一般是因为数量太多)的嫌疑对象 必要时,需要分析嫌疑对象和其他对象的引用关系. 查看程序的源代码,找出嫌疑对象数量过多的原因. dum

  • php没有文件被上传的实例分析及解决办法

    1.修改php.ini,设置上传文件的大小. 2.在httpd.conf中添加"php_value upload_max_filesize "300M"". 3.重启服务器即可. 使用ThinkPhp框架上传小图片文件成功,上传大文件失败. 后来查找了原因,是因为php限制了上传文件的大小,修改php.ini如下配置: upload_max_filesize = 300M post_max_size = 300M 重启服务器,依然如此,问题并未得到解决. 解决方法如

随机推荐