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);