c++ - 求最经典的01背包算法PHP或Javascript实现方案

问题描述

问 题

一个典型01背包问题（动态规划法解决）题目

---

丰丰快递每天能收到成千上万的物流单，每个物流单的重量不一。 现在丰丰快递的货车司机隔壁老王开着丰丰的标配货车（限载5吨，含5吨，不考虑限高）,想要一次性拿走尽可能重的货物，这些货有红木沙发，有钢材等等。

---

以下是货物清单：

货物编号	货物重量(单位:kg)
1	509
2	838
3	924
4	650
5	604
6	793
7	564
8	651
9	697
10	649
11	747
12	787
13	701
14	605
15	644

---

比如 1-2-3代表同时装入编号为1,2,3的货物，此时货物总重为509（1号货物）+838（2号货物）+924（3号货物）=2271kg,远小于限载额——5吨，隔壁老王会被吐槽的。。。

比如1-5-8-9-11-12-14代表同时装入编号为1,5,8,9，11,12,14的货物，此时货物总重为509（1号货物）+604（5号货物）+651（8号货物）+697（9号货物）747（11号货物）+787（12号货物）+605（14号货物）=4600kg，这时与限载额——5吨，就比较接近了，隔壁老王会很高兴。。。

---

也就是找出最接近5000kg的那一段组合，典型的背包01问题

在下才疏学浅，用最笨的方法实现出来了，但是还望大佬指点正确的背包01用php或者javascript的实现方案，因为网上教程那些数学符号太操蛋了，看不懂啊！！！ 有相同爱好的小伙伴恳请帮邀些大佬来指点一下，共同学习

//货物
$cargo = [
   '1'  => '509',
   '2'  => '838',
   '3'  => '924',
   '4'  => '650',
   '5'  => '604',
   '6'  => '793',
   '7'  => '564',
   '8'  => '651',
   '9'  => '697',
   '10' => '649',
   '11' => '747',
   '12' => '787',
   '13' => '701',
   '14' => '605',
   '15' => '644'
];

$sum   = '';
$str   = '';
$statistics   = 0;

// 开始装货
makeCargo( $cargo );

/**
 * [makeCargo 装货]
 * @author     Shaowei Pu <[e-mail]>
 * @CreateTime  2017-02-14T19:00:21+0800
 * @param                               array   $cargo       [装货数组]
 * @param                               integer $current_key [当前数组key]
 * @param                               integer $current_num [当前value]
 * @param                               string  $string      [此次拼接字符串]
 * @return                              [type]               [最终递归到的字符]
 */
function makeCargo( $cargo = [] ,$current_key = 1, $current_num = 0, $string = '')
{
    global $sum,$str,$statistics;
   
    // 调用统计
    $statistics ++;
    // 中间数
    if( $current_num >= $sum  ){
      $sum = $current_num; 
      $str = $string;
    }
    // 若置空
    if( empty($cargo) ) return;

    // 空容器作替换，当前容器内为当前传递数字 + 上一个传递数
    $container = $cargo[$current_key] + $current_num ;

    // 数组中删掉数 避免再次拿出
    unset($cargo[$current_key]);

    // 当前容器组合 <= 5000 
    if( $container <= 5000 )
      makeCargo( $cargo ,$current_key+1, $container,$string.'-'.$current_key);
  // 
  makeCargo( $cargo ,$current_key+1, $current_num,$string );
}   
echo $statistics;
var_dump($sum,$str);

解决方案

//货物
$cargo = [
   '1'  => '509',
   '2'  => '838',
   '3'  => '924',
   '4'  => '650',
   '5'  => '604',
   '6'  => '793',
   '7'  => '564',
   '8'  => '651',
   '9'  => '697',
   '10' => '649',
   '11' => '747',
   '12' => '787',
   '13' => '701',
   '14' => '605',
   '15' => '644'
];

$sum   = '';
$str   = '';
$statistics   = 0;

// 开始装货
makeCargo( $cargo );

/**
 * [makeCargo 装货]
 * @author     Shaowei Pu <[e-mail]>
 * @CreateTime  2017-02-14T19:00:21+0800
 * @param                               array   $cargo       [装货数组]
 * @param                               integer $current_key [当前数组key]
 * @param                               integer $current_num [当前value]
 * @param                               string  $string      [此次拼接字符串]
 * @return                              [type]               [最终递归到的字符]
 */
function makeCargo( $cargo = [] ,$current_key = 1, $current_num = 0, $string = '')
{
    global $sum,$str,$statistics;
   
    // 调用统计
    $statistics ++;
    // 中间数
    if( $current_num >= $sum  ){
      $sum = $current_num; 
      $str = $string;
    }
    // 若置空
    if( empty($cargo) ) return;

    // 空容器作替换，当前容器内为当前传递数字 + 上一个传递数
    $container = $cargo[$current_key] + $current_num ;

    // 数组中删掉数 避免再次拿出
    unset($cargo[$current_key]);

    // 当前容器组合 <= 5000 
    if( $container <= 5000 )
      makeCargo( $cargo ,$current_key+1, $container,$string.'-'.$current_key);
  // 
  makeCargo( $cargo ,$current_key+1, $current_num,$string );
}   
echo $statistics;
var_dump($sum,$str);

这篇关于c++ - 求最经典的01背包算法PHP或Javascript实现方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！