求个php算法

Question

本人一直做业务,算法很少碰到,基本是不会算法
现求个php的算法.
有一个固定大小包, 规定能装1000元价值物品
有一堆物品,

玩具车1    每个100元   有10个
玩具车2    每个200元   有5个
玩具车3    每个300元   有4个

通过算法可以很快的知道装满或者最多装下多少件不同商品,要求商品可以以最高价值,或者最低价值 的组合来

好比: 最高价值组合

玩具车3    每个300元  * 3件
玩具车1    每个100元  * 1件

  最低价值组合
玩具车1    每个100元  * 10件

但是要考虑到有这样的情况

如果物品数量是这样的情况:

玩具车1    每个100元   有10个
玩具车2    每个200元   有1个
玩具车3    每个300元   有2个

那么最高价值组合可能是这样取的 (因为玩具车3只有2件,接着取玩具车2来凑数,还不够,继续取玩具车1来凑满,这样类推下去,知道取的值刚好到1000或者最接近1000)
玩具车3    每个300元   * 2
玩具车2    每个200元   * 1
玩具车1    每个100元   * 3
    

Answer 1

01背包问题。运用动态规划就可以解决。

Answer 2

题主的题目描述太模糊了。
能否装满，最多装下多少件不同商品，在装满的前提下最多装下多少件不同的商品，不同的问题有不同的解决方法。
而且在题目中，我没看出来价格有什么作用。
我这里尝试给出在装满的前提下最多能装下多少件不同的商品的代码，如有不对，欢迎指正。

<?php

$bag     = array();
$objects = array(
    array('w' => 100, 'p' => 100),
    array('w' => 200, 'p' => 200),
    array('w' => 300, 'p' => 300),
    array('w' => 400, 'p' => 400),
    array('w' => 500, 'p' => 500)
);

//初始化包的状态,-1没有组合成这个大小的包的组合方案
for ($i = 1; $i <= 1000; $i++) {
    $bag[$i] = -1;
}

//空包肯定是存在解决方案的,放入0件物品
$bag[0] = 0;
for ($i = 0; $i <= 4; $i++) {
    for ($j = 1000; $j >= $objects[$i]['w']; $j--) {
        //假如$bag[$j - $objects[$i]['w']]存在组合方案,那就与当前$bag[$j]的组合方案比较,取其中物品件数较多的那种
        if($bag[$j - $objects[$i]['w']] != -1) {
            $bag[$j] = $bag[$j - $objects[$i]['w']] + 1 > $bag[$j] ? $bag[$j - $objects[$i]['w']] + 1 : $bag[$j];
        }
    }
}

echo $bag[1000] == -1 ? "不存在装满包的解决方案" : "在保证装满的前提下,最多可以装{$bag[1000]}件物品";

题主修改了题目的意思，我这里给出的是在确定包容量、物品数量不限，求包最大价值的代码。
最小价值的话存在一个歧义，就是空包价值为0，已经是最小价值了。
限制物品数量的情况，可以参考我第一次给出的代码，直接把所有物品视为数量为1的独立的商品，修改上面的代码应该就可以得到结果（但是在物品数量较大的情况下，需要考虑做一些优化，因为优化方案不影响解题本身的思路，就不单独写出了）。

<?php

$bag     = array();
$objects = array(
    array('w' => 100, 'p' => 100),
    array('w' => 200, 'p' => 200),
    array('w' => 300, 'p' => 300),
    array('w' => 400, 'p' => 400),
    array('w' => 500, 'p' => 500)
);

//初始化包的状态,初始价值都为0
for ($i = 0; $i <= 1000; $i++) {
    $bag[$i] = 0;
}

for ($i = 0; $i <= 4; $i++) {
    for ($j = $objects[$i]['w']; $j <= 1000; $j++) {
        $bag[$j] = $bag[$j] > $bag[$j - 1] ? $bag[$j] : $bag[$j - 1];
        $bag[$j] = $bag[$j - $objects[$i]['w']] + $objects[$i]['p'] > $bag[$j] ? $bag[$j - $objects[$i]['w']] + $objects[$i]['p'] : $bag[$j];
    }
}

echo "最多可以装{$bag[1000]}价值的物品";

如有错误，欢迎指正。