php - 获得给定数组中组合总和的最低价格

Question

当数组长度仅为 8 或 10 时，此代码可以正常工作。当我们检查超过 10 个数组长度的相同代码时，它会加载而不显示结果。

如何减少我的代码。如果你有算法请分享。请帮助我。

本程序工作流程:

$allowed_per_room_accommodation =[2,3,6,5,3,5,2,5,4];
$allowed_per_room_price =[10,30,60,40,30,50,20,60,80];
$search_accommodation = 10;

我得到子集 = [5,5],[5,3,2],[6,4],[6,2,2],[5,2,3],[3,2,5 ]

显示最低价格的房间，然后等于 10 个住宿；输出如 [5,3,2];

<?php 
    $dp=array(array());
    $GLOBALS['final']=[];
    $GLOBALS['room_key']=[];
    function display($v,$room_key) 
    {   
        $GLOBALS['final'][] = $v;
        $GLOBALS['room_key'][] = $room_key;
    }

    function printSubsetsRec($arr, $i, $sum, $p,$dp,$room_key='') 
    { 

        // If we reached end and sum is non-zero. We print 
        // p[] only if arr[0] is equal to sun OR dp[0][sum] 
        // is true. 
        if ($i == 0 && $sum != 0 && $dp[0][$sum]) { 
            array_push($p,$arr[$i]);
            array_push($room_key,$i);
            display($p,$room_key);
            return $p; 
        } 

        // If $sum becomes 0 
        if ($i == 0 && $sum == 0) { 
            display($p,$room_key);
            return $p; 
        } 

        // If given sum can be achieved after ignoring 
        // current element. 
        if (isset($dp[$i-1][$sum])) { 
            // Create a new vector to store path 

            // if(!is_array(@$b))
            // $b = array();
            $b = $p;
            printSubsetsRec($arr, $i-1, $sum, $b,$dp,$room_key); 
        } 


        // If given $sum can be achieved after considering 
        // current element. 
        if ($sum >= $arr[$i] && isset($dp[$i-1][$sum-$arr[$i]]))
        { 
            if(!is_array($p))
                $p = array();
            if(!is_array($room_key))
                $room_key = array();
            array_push($p,$arr[$i]);
            array_push($room_key,$i);
            printSubsetsRec($arr, $i-1, $sum-$arr[$i], $p,$dp,$room_key); 
        } 
    } 


    // Prints all subsets of arr[0..n-1] with sum 0. 
    function printAllSubsets($arr, $n, $sum,$get=[]) 
    { 
        if ($n == 0 || $sum < 0) 
            return; 
        // Sum 0 can always be achieved with 0 elements 
        // $dp = new bool*[$n]; 
        $dp = array(); 
        for ($i=0; $i<$n; ++$i) 
        { 
            // $dp[$i][$sum + 1]=true;
            $dp[$i][0] = true; 
        } 
        // Sum arr[0] can be achieved with single element 
        if ($arr[0] <= $sum) 
            $dp[0][$arr[0]] = true; 
        // Fill rest of the entries in dp[][] 
        for ($i = 1; $i < $n; ++$i) {
            for ($j = 0; $j < $sum + 1; ++$j) {
                // echo $i.'d'.$j.'.ds';
                $dp[$i][$j] = ($arr[$i] <= $j) ? (isset($dp[$i-1][$j])?$dp[$i-1][$j]:false) | (isset($dp[$i-1][$j-$arr[$i]])?($dp[$i-1][$j-$arr[$i]]):false) : (isset($dp[$i - 1][$j])?($dp[$i - 1][$j]):false);
            }
        }
        if (isset($dp[$n-1][$sum]) == false) { 
            return "There are no subsets with";  
        } 

        $p; 
        printSubsetsRec($arr, $n-1, $sum, $p='',$dp); 
    } 

    $blockSize = array('2','3','6','5','3','5','2','5','4');
    $blockvalue = array('10','30','60','40','30','50','20','60','80');
    $blockname = array("map","compass","water","sandwich","glucose","tin","banana","apple","cheese");
    $processSize = 10; 
    $m = count($blockSize); 
    $n = count($processSize); 
    // sum of sets in array
    printAllSubsets($blockSize, $m, $processSize);
    $final_subset_room = '';
    $final_set_room_keys = '';
    $final_set_room =[];
    if($GLOBALS['room_key']){
        foreach ($GLOBALS['room_key'] as $set_rooms_key => $set_rooms) {
            $tot = 0;
            foreach ($set_rooms as  $set_rooms) {
                $tot += $blockvalue[$set_rooms];
            }
            $final_set_room[$set_rooms_key] = $tot;
        }
    asort($final_set_room);
    $final_set_room_first_key = key($final_set_room);
    $final_all_room['set_room_keys'] = $GLOBALS['room_key'][$final_set_room_first_key];
    $final_all_room_price['set_room_price'] = $final_set_room[$final_set_room_first_key];
    }
    if(isset($final_all_room_price)){
        asort($final_all_room_price);
        $final_all_room_first_key = key($final_all_room_price);
        foreach ($final_all_room['set_room_keys'] as  $key_room) {
            echo $blockname[$key_room].'---'. $blockvalue[$key_room]; 
            echo '<br>';
        }
    }
    else
        echo 'No Results';
?>

Answer 1

我假设你的任务是，给定一个房间列表，每个房间都有它可以容纳的人数和价格，以容纳 10 人(或任何其他数量)。

这个问题类似于0-1 knapsack problem这在多项式时间内是可解的。在背包问题中，一个目标是最大化价格，这里我们的目标是最小化它。与经典背包问题不同的另一件事是，即使房间没有完全被占用，也会收取全房费用。它可能会降低维基百科上提出的算法的有效性。无论如何，如果您以前从未使用过动态规划，那么实现就不会那么简单。

想了解更多，CLRS book on algorithms第 15 章讨论动态规划，第 16 章讨论背包问题。在后一章中，他们还证明了 0-1 背包问题没有平凡的贪婪解。