我遇到了一个问题，我会尽量用最简单的术语来描述它。
使用PHP和MySQL的组合，我需要解决以下逻辑问题，这是所需内容的简化版本，但简而言之，逻辑是相同的。
思考框。我有很多小盒子，还有一个大盒子。我需要能够用很多小盒子装满这个大盒子。
所以让我们来分解一下。
我在MySQL中有一个表，它有以下行
Table: small_boxes
id | box_size
=============
1 | 100
2 | 150
3 | 200
4 | 1000
5 | 75
..etc
这张表可以多达数百个，有些盒子的大小相同
例如，我现在需要用我在表中找到的所有small_boxes的组合来填充一个800大小的大框。大盒子可以是用户想要填充的任何大小。
这里的目标不是效率，例如，我真的不在乎稍微低一点或稍微高一点，只是在公差范围内显示可能适合的盒子的不同变体。
因此，如果可能的话，我想了解如何在PHP/MMySQL中解决这个问题。我在这两方面都很胜任，但问题在于我如何处理。
举一些例子会很棒，但我很乐意接受一些信息来让我开始。
您可能应该研究一下光荣的背包问题
https://codegolf.stackexchange.com/questions/3731/solve-the-knapsack-problem
请仔细阅读。
希望你选修了代数2.
以下是一些可能对您有所帮助的PHP代码：
http://rosettacode.org/wiki/Knapsack_problem/0-1#PHP
感谢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);