PHP实现动态规划背包问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP实现动态规划背包问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1009字，纯文字阅读大概需要2分钟。

内容图文

有一堆货物，有各种大小和价值不等的多个物品，而你只有固定大小的背包，拿走哪些能保证你的背包带走的价值最多

动态规划就是可以记录前一次递归过程中计算出的最大值，在之后的递归期间使用，以免重复计算。

<?php                                                                                                                                        
 
$thing_arr = array(
    array('size' => 9, 'weight' =>10),
    array('size' => 4, 'weight' => 5), 
    array('size' => 6, 'weight' => 4), 
    array('size' => 7, 'weight' => 9), 
);
 
$max_package_arr = array();
$max_thing_arr   = array();
 
function package($space)
{
    global $thing_arr, $max_package_arr, $max_thing_arr;
    if (isset($max_package_arr[$space])) return $max_package_arr[$space];
    $max_value = 0;
    foreach($thing_arr as $thing) 
    {   
        if (($rest_space = $space-$thing['size'])>0)
        {   
            if (($value = package($rest_space) + $thing['weight']) > $max_value )
            {   
                $max_package_arr[$space] = $max_value = $value;
                $max_thing_arr[$space] = $thing['weight'];
            }   
        }   
    }   
    return $max_value;
}
 
 
echo package(12);
print_r($max_thing_arr);

内容总结

以上是互联网集市为您收集整理的PHP实现动态规划背包问题全部内容，希望文章能够帮你解决PHP实现动态规划背包问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端