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)指上一个最优解

<?php
//这是我根据动态规划原理写的
// max(opt(i-1,w),wi+opt(i-1,w-wi))
//背包可以装最大的重量
$w=15;
//这里有四件物品,每件物品的重量
$dx=array(3,4,5,6);
//每件物品的价值
$qz=array(8,7,4,9);
//定义一个数组
$a=array();
//初始化
for($i=0;$i<=15;$i++){ $a[0][$i]=0; }
for ($j=0;$j<=4;$j++){ $a[$j][0]=0; }
//opt(i-1,w),wi+opt(i-1,w-wi)
for ($j=1;$j<=4;$j++){
  for($i=1;$i<=15;$i++){
    $a[$j][$i]=$a[$j-1][$i];
    //不大于最大的w=15
    if($dx[$j-1]<=$w){
      if(!isset($a[$j-1][$i-$dx[$j-1]])) continue;
      //wi+opt(i-1,wi)
      $tmp = $a[$j-1][$i-$dx[$j-1]]+$qz[$j-1];
      //opt(i-1,w),wi+opt(i-1,w-wi) => 进行比较
      if($tmp>$a[$j][$i]){
        $a[$j][$i]=$tmp;
      }
    }
  }
}
//打印这个数组,输出最右角的值是可以最大价值的
for ($j=0;$j<=4;$j++){
  for ($i=0;$i<=15;$i++){
    echo $a[$j][$i]."/t";
    } echo "/n";
}
?>

希望本文所述对大家的php程序设计有所帮助。

赞 (0)

相关推荐

  • 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;

  • 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;

  • 关于背包问题的一些理解和应用

    关于背包问题的一些理解和应用

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

  • 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

  • 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#用递归算法解决经典背包问题

    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)指上一个最优解

  • 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上打出

  • 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 重启服务器,依然如此,问题并未得到解决. 解决方法如

  • php中Y2K38的漏洞解决方法实例分析

    本文实例分析了php中Y2K38漏洞的解决方法.分享给大家供大家参考.具体分析如下: Y2K38,又称 Unix Millennium Bug, 此漏洞将会影响到所有 32 位系统下用 UNIX 时间戳整数来记录时间的 PHP,及其它编程语言. 一个整型的变量所能保存的最大时间为 2038 年 1 月 19 日 03:14:07.超过这个时间后,整型数值将会溢出. 从 1970 年 01 月 01 日开始,到世界标准时 2038 年 01 月 19 日星期二凌晨 03:14:07 超过 2^31

随机推荐