6

我遇到了一个问题，我会尽量用最简单的术语来描述它。

使用 PHP 和 MySQL 的组合我需要完成以下逻辑问题，这是所需内容的简化版本，但简而言之，逻辑是相同的。

思考框。我有很多小盒子，一个大盒子。我需要能够使用许多小盒子来填充大盒子。

所以让我们分解一下。

我在 MySQL 中有一个表，其中包含以下行

Table: small_boxes
id | box_size
=============
1  | 100
2  | 150
3  | 200
4  | 1000
5  | 75
..etc

这张桌子可以多达数百个，有些盒子的大小相同

我现在需要填充一个大小为 800 的大盒子，其中包含我在表中找到的所有 small_boxes 组合。大框可以是用户希望填充的任何大小。

这里的目标不是效率，例如，我并不真正关心稍微低于或略高于，只是在公差数字内显示可能适合的盒子的不同变化。

所以如果可能的话，我想了解如何在 PHP/MySQL 中解决这个问题。我在这两方面都很有能力，但问题在于我如何处理这个问题。

例子会很棒，但我很乐意接受一些信息来帮助我开始。

4

3 回答 3

3

您可能应该研究一下光荣的背包问题

于 2012-07-09T15:30:12.977 回答
2

https://codegolf.stackexchange.com/questions/3731/solve-the-knapsack-problem

阅读此内容。

希望你学过代数2..

以下是一些可能对您有所帮助的 PHP 代码：

http://rosettacode.org/wiki/Knapsack_problem/0-1#PHP

于 2012-07-09T15:42:27.523 回答
1

感谢 maxhd 和 Ugo Meda 为我指明了正确的方向！

结果，我得到了非常接近我需要的东西。我不确定这是否属于“背包问题”或其任何变体，但这是我提出的代码。随意向我提出任何建设性的批评！

为了尝试在背包内获得一些不同的盒子变体，我已经删除了每个主循环迭代中最大的项目，再次，如果有更好的方法，请告诉我:)

谢谢！

class knapsack {
    private $items;
    private $knapsack_size;
    private $tolerance = 15; //Todo : Need to make this better, perhaps a percentage of knapsack
    private $debug = 1;

    public function set_knapsack_size($size){
        $this->knapsack_size = $size;
    }

    public function set_items($items){
        if(!is_array($items)){
            return false;
        }

        //Array in the format of id=>size, ordered by largest first
        $this->items = $items;
    }

    public function set_tolerance($tolerance){
        $this->tolerance = $tolerance;
    }

    private function remove_large_items(){
        //Loop through each of the items making sure we can use this sized item in the knapsack
        foreach($this->items as $list_id=>$list){
            //Lets look ahead one, and make sure it isn't the last largest item, we will keep largest for oversize.
            if($list["size"] > $this->knapsack_size && (isset($this->items[$list_id+1]) && $this->items[$list_id+1]["size"] > $this->knapsack_size)){
                unset($this->items[$list_id]);
            }else{
                //If we ever get here, simply return true as we can start to move on
                return true;
            }
        }

        return true;
    }

    private function append_array($new_data,$array){
        if(isset($array[$new_data["id"]])){
            $array[$new_data["id"]]["qty"]++;
        }else{
            $array[$new_data["id"]]["qty"] = 1;
        }

        return $array;
    }

    private function process_items(&$selected_items,$knapsack_current_size){
        //Loop the list of items to see if we can fit it in the knapsack
        foreach($this->items as $list){
            //If we can fit the item into the knapsack, lets add it to our selected_items, and move onto the next item
            if($list["size"] <= $knapsack_current_size){

                $this->debug("Knapsack size is : ".$knapsack_current_size." - We will now take ".$list["size"]." from it");
                $selected_items = $this->append_array($list,$selected_items);
                $knapsack_current_size -= $list["size"];

                //Lets run this method again, start recursion
                $knapsack_current_size = $this->process_items($selected_items,$knapsack_current_size);
            }else{
                //Lets check if we can fit a slightly bigger item into the knapsack, so we can eliminate really small items, within tolerance
                if(($list["size"] <= $knapsack_current_size + $this->tolerance) && $knapsack_current_size > 0){
                    $this->debug("TOLERANCE HIT : Knapsack size is : ".$knapsack_current_size." - We will now take ".$list["size"]." from it");
                    $selected_items = $this->append_array($list,$selected_items);
                    $knapsack_current_size -= $list["size"];
                }
            }

            //Lets see if we have to stop the recursion
            if($knapsack_current_size < 0){
                return $knapsack_current_size;
            }
        }
    }

    private function debug($message=""){
        if(!$this->debug){
            return false;
        }

        echo $message."\n";
    }

    public function run(){
        //If any of the variables have not been set, return false
        if(!is_array($this->items) || !$this->knapsack_size){
            return false;
        }

        //Lets first remove any items that may be too big for the knapsack
        $this->remove_large_items();

        //Lets now check if we still have items in the array, just incase the knapsack is really small
        if(count($this->items) == 0){
            return false;
        }

        //Now that we have a good items list, and we have no items larger than the knapsack, lets move on.
        $variants = array();
        foreach($this->items as $list_id=>$list){
            $this->debug();
            $this->debug("Finding variants : ");

            $selected_items = array();
            $this->process_items($selected_items,$this->knapsack_size);
            $variants[] = $selected_items;

            //Remove the largest variant, so we get a new set of unique results
            unset($this->items[$list_id]);
        }

        return $variants;
    }
}

$products = array(
    array("id"=>1,"size"=>90),
    array("id"=>2,"size"=>80),
    array("id"=>3,"size"=>78),
    array("id"=>4,"size"=>66),
    array("id"=>5,"size"=>50),
    array("id"=>6,"size"=>42),
    array("id"=>7,"size"=>36),
    array("id"=>8,"size"=>21),
    array("id"=>9,"size"=>19),
    array("id"=>10,"size"=>13),
    array("id"=>11,"size"=>7),
    array("id"=>12,"size"=>2),
);

$knapsack = new knapsack();
$knapsack->set_items($products);
$knapsack->set_knapsack_size(62);
$result = $knapsack->run();

var_dump($result);
于 2012-07-10T00:21:43.440 回答