search
HomeBackend DevelopmentPHP Tutorial请教各位大神一个变形的背包问题

有N种物品和一个容量为V的背包。还有一个阈值T。
第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和大于且最接近T。

附完全背包代码

        /** 
    *背包问题描述:一个承受最大重量为W的背包,现在有n个物品,每个物品重量为t, 每个物品的价值为v。 
    * 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大。 
    *思路:定义一个二维数组,一维为物品数量(表示每个物品),二维是重量(不超过最大,这里是10),下面数组a, 
    *动态规划原理思想,max(opt(i-1,w),wi+opt(i-1,w-wi)) 当中最大值, 
    *opt(i-1,w-wi)指上一个最优解 
    */  
    //这是我根据动态规划原理写的   
    // max(opt(i-1,w),wi+opt(i-1,w-wi))   
    //背包可以装最大的重量   
    $w=10;   
    //这里有四件物品,每件物品的重量   
    $dx=array(3,4,5);   
    //每件物品的价值   
    $qz=array(4,5,6);   
    //定义一个数组   
    $a=array();   
    //初始化   
    for($i=0;$i     for ($j=0;$j     //opt(i-1,w),wi+opt(i-1,w-wi)   
    for ($j=1;$j         for($i=1;$i             $a[$j][$i]=$a[$j-1][$i];   
            //不大于最大的w=10  
            if($dx[$j-1]                 if(!isset($a[$j-1][$i-$dx[$j-1]])) continue;  
                //wi+opt(i-1,wi)  
                $tmp = $a[$j-1][$i-$dx[$j-1]]+$qz[$j-1];   
                //opt(i-1,w),wi+opt(i-1,w-wi) => 进行比较    
                if($tmp>$a[$j][$i]){   
                    $a[$j][$i]=$tmp;   
                }   
            }   
        }   
    }   
    //打印这个数组,输出最右角的值是可以最大价值的   
    for ($j=0;$j         for ($i=0;$i             echo $a[$j][$i]."    ";   
            } echo "
";   
    } 


    ?>  


回复讨论(解决方案)

你遇到了什么问题呢?你的结果应该是对的
不过我喜欢这么写

$w = 10;$ar = array(  array('w' => 3, 'v' => 4),  array('w' => 4, 'v' => 5),  array('w' => 5, 'v' => 6),);foreach($ar as $k=>$v) {  $v['k'][] = $k;  $res[] = $v;}$p = 0;for(;$p<count($res); $p++) {  $r = $res[$p];  foreach($ar as $i=>$v) {    if(in_array($i, $res[$p]['k'])) continue;    if($r['w'] + $v['w'] <= $w) {      $res[] = array(        'w' => $r['w'] + $v['w'],        'v' => $r['v'] + $v['v'],        'k' => array_merge($r['k'], array($i)),      );    }  }}foreach($res as $v) $t[] = $v['v'];array_multisort($t, SORT_DESC, $res); print_r($res);
Array(    [0] => Array        (            [w] => 9            [v] => 11            [k] => Array                (                    [0] => 1                    [1] => 2                )        )    [1] => Array        (            [w] => 9            [v] => 11            [k] => Array                (                    [0] => 2                    [1] => 1                )        )    [2] => Array        (            [w] => 8            [v] => 10            [k] => Array                (                    [0] => 0                    [1] => 2                )        )    [3] => Array        (            [w] => 8            [v] => 10            [k] => Array                (                    [0] => 2                    [1] => 0                )        )    [4] => Array        (            [w] => 7            [v] => 9            [k] => Array                (                    [0] => 0                    [1] => 1                )        )    [5] => Array        (            [w] => 7            [v] => 9            [k] => Array                (                    [0] => 1                    [1] => 0                )        )    [6] => Array        (            [w] => 5            [v] => 6            [k] => Array                (                    [0] => 2                )        )    [7] => Array        (            [w] => 4            [v] => 5            [k] => Array                (                    [0] => 1                )        )    [8] => Array        (            [w] => 3            [v] => 4            [k] => Array                (                    [0] => 0                )        ))

目前这个是 装满了w=10的背包的最大价值。

我是想找出:在尽量装满背包的情况下,总价值接近给定的一个阈值T  的组合

$f = 9;print_r(array_filter($res, function($a) use ($f) { return $a['v'] > 0.9*$f && $a['v']<1.1*$f;}));


太强了,感谢版主大人!非常牛B,结果完全达到了

这个算法你写的太简洁了,有点看不懂,再请教您一下,怎么过滤掉重复的组合啊? 比如  0 3 6  ,3 0 6,6 0 3

....array_multisort($t, SORT_DESC, $res); //排序(已有的)foreach($res as $i=>$v) if(isset($res[$i-1]) && ! array_diff($res[$i-1]['k'], $v['k'])) unset($res[$i]); //去重$res = array_values($res); //规格化


我这个算法并未完全按照动态规划去做
而是记录了所有可能的组合,最后用排序做检查

太感谢了,多谢您的指教

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
11 Best PHP URL Shortener Scripts (Free and Premium)11 Best PHP URL Shortener Scripts (Free and Premium)Mar 03, 2025 am 10:49 AM

Long URLs, often cluttered with keywords and tracking parameters, can deter visitors. A URL shortening script offers a solution, creating concise links ideal for social media and other platforms. These scripts are valuable for individual websites a

Introduction to the Instagram APIIntroduction to the Instagram APIMar 02, 2025 am 09:32 AM

Following its high-profile acquisition by Facebook in 2012, Instagram adopted two sets of APIs for third-party use. These are the Instagram Graph API and the Instagram Basic Display API.As a developer building an app that requires information from a

Working with Flash Session Data in LaravelWorking with Flash Session Data in LaravelMar 12, 2025 pm 05:08 PM

Laravel simplifies handling temporary session data using its intuitive flash methods. This is perfect for displaying brief messages, alerts, or notifications within your application. Data persists only for the subsequent request by default: $request-

Build a React App With a Laravel Back End: Part 2, ReactBuild a React App With a Laravel Back End: Part 2, ReactMar 04, 2025 am 09:33 AM

This is the second and final part of the series on building a React application with a Laravel back-end. In the first part of the series, we created a RESTful API using Laravel for a basic product-listing application. In this tutorial, we will be dev

Simplified HTTP Response Mocking in Laravel TestsSimplified HTTP Response Mocking in Laravel TestsMar 12, 2025 pm 05:09 PM

Laravel provides concise HTTP response simulation syntax, simplifying HTTP interaction testing. This approach significantly reduces code redundancy while making your test simulation more intuitive. The basic implementation provides a variety of response type shortcuts: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

cURL in PHP: How to Use the PHP cURL Extension in REST APIscURL in PHP: How to Use the PHP cURL Extension in REST APIsMar 14, 2025 am 11:42 AM

The PHP Client URL (cURL) extension is a powerful tool for developers, enabling seamless interaction with remote servers and REST APIs. By leveraging libcurl, a well-respected multi-protocol file transfer library, PHP cURL facilitates efficient execution of various network protocols, including HTTP, HTTPS, and FTP. This extension offers granular control over HTTP requests, supports multiple concurrent operations, and provides built-in security features.

12 Best PHP Chat Scripts on CodeCanyon12 Best PHP Chat Scripts on CodeCanyonMar 13, 2025 pm 12:08 PM

Do you want to provide real-time, instant solutions to your customers' most pressing problems? Live chat lets you have real-time conversations with customers and resolve their problems instantly. It allows you to provide faster service to your custom

Announcement of 2025 PHP Situation SurveyAnnouncement of 2025 PHP Situation SurveyMar 03, 2025 pm 04:20 PM

The 2025 PHP Landscape Survey investigates current PHP development trends. It explores framework usage, deployment methods, and challenges, aiming to provide insights for developers and businesses. The survey anticipates growth in modern PHP versio

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment