// 需要覆盖省的集合
$provinceNeed = array('bj', 'tj', 'hb', 'sd', 'sx', 'hn', 'hub', 'hlj', 'jn', 
	'ln', 'ah', 'zj', 'gd', 'gx', 'js', 'fj', 'yn', 'nmg', 'shx', 'xz', 
	'xj', 'gs', 'sc', 'cq', 'qh', 'sh', 'jx');

// asort($provinceNeed);
// print_r($provinceNeed);

// 电视台及其覆盖的省的集合.为方便测试,假设电视台只覆盖相邻的几个省.只简单写了几个数据
$stations = array();
$stations['bj'] = array('bj', 'tj', 'hb', 'sd', 'nmg');
$stations['hlj'] = array('bj', 'tj', 'hlj', 'jn', 'ln');
$stations['ln'] = array('bj', 'tj', 'hlj', 'jn', 'ln', 'sd');
$stations['tj'] = array('tj', 'hb', 'sx', 'hn');
$stations['sd'] = array('sd', 'sx', 'hn', 'ln', 'js', 'ah', 'zj');
$stations['hb'] = array('hb', 'sd', 'sx', 'hn', 'shx', 'nmg', 'sx', 'ah');
$stations['sx'] = array('sd', 'sx', 'sc', 'nmg', 'xj');
$stations['cq'] = array('sc', 'cq', 'hb', 'gx', 'gd', 'xj');
$stations['xj'] = array('xj', 'xz', 'qh', 'nmg', 'gs');
$stations['hub'] = array('sc', 'hn', 'sh', 'gd', 'yn', 'hub');
$stations['sh'] = array('sh', 'fj', 'sd', 'gd', 'gx', 'js', 'jx', 'zj');

// 最终的电台列表
$finalStation = array();

while (count($provinceNeed) > 0){
	// 当前最佳的选择:包含未覆盖省最多的电台
	$bestStation = NULL;
	// 已经覆盖的省的列表
	$provonceCovered = array();
	
	// 遍历所有电台.选一个电台，它覆盖了最多的未覆盖的省
	foreach ($stations as $province => $provinceStationList) {
		$covered = array_unique(array_intersect($provinceNeed, $provinceStationList));
		
		if(count($covered) > count($provonceCovered)){
			$bestStation = $province;
			$provonceCovered = $covered;
		}
	}
	
	$provinceNeed = array_diff($provinceNeed, $provonceCovered);
	array_push($finalStation, $bestStation);
}

print_r($finalStation);

Array
(
    [0] => sh
    [1] => hb
    [2] => hlj
    [3] => xj
    [4] => hub
    [5] => cq
)

<?php

$bagMax = 35;
// 待解析的商品.顺序可以打乱
$goods = array('R', 'T', 'H', 'B');

$weight['R'] = 15;
$weight['T'] = 20;
$weight['H'] = 30;
$weight['B'] = 5;

$value['R'] = 1500;
$value['T'] = 2000;
$value['H'] = 3000;
$value['B'] = 5000;

$bagList = array();
// 划分背包为各个小包,即表格的列.比如以 5 为区间递减
for ($i = 35; $i > 0; $i -= 5) {
    array_push($bagList, $i);
}
asort($bagList);
// print_r($bagList);
// 双重循环填充表格
$info = array();
// 用来存放不同容量包裹的最大价值及物品及各列的信息.为了方便查询
$maxInfo = array();

foreach ($goods as $loopGoods) {
    foreach ($bagList as $loopBag) {
        // 1. 如果刚好能放下当前物品.直接设置当前信息为当前商品
        // 2. 如果当前容量放不下当前物品.找当前容量下最大价值的商品.把它作为当前位置的商品信息
        // 3. 如果当前容量大于当前商品占位.先把当前商品加上,然后在找剩余重量对应的最大价值商品并加上
        // 4. 把当前位置的信息添加到列信息和表格信息中

        // 需要查找的额外的商品的信息
        $addValue = 0;
        $addGood = array();
        // 基础商品信息
        $baseValue = 0;
        $baseGood = array();

        // 要去查找的商品的重量
        $toFindWeight = 0;

        if ($loopBag >= $weight[$loopGoods]) {
            $toFindWeight = $loopBag - $weight[$loopGoods];

            $baseValue = $value[$loopGoods];
            array_push($baseGood, $loopGoods);
        } else {
            $toFindWeight = $loopBag;
        }

        // 去找附加商品的信息
        if ($toFindWeight > 0 && array_key_exists($toFindWeight, $maxInfo)) {
            foreach ($maxInfo[$toFindWeight] as $maxgood => $maxgoodinfo) {
                $loopValue = $maxgoodinfo['value'];
                $loopGood = $maxgoodinfo['goods'];

                // 和当前商品相同的不添加.意思是一个格子里不能添加两个相同的商品
                if ($maxgood == $loopGoods) {
                    continue;
                }
                // 找到价值最大的商品
                if ($loopValue > $addValue) {
                    $addValue = $loopValue;
                    $addGood = $loopGood;
                }
            }
        }

        // 设置表格信息和列信息
        $info[$loopGoods][$loopBag]['value'] = $baseValue + $addValue;
        $info[$loopGoods][$loopBag]['goods'] = array_merge($baseGood, $addGood);

        $maxInfo[$loopBag][$loopGoods]['value'] = $info[$loopGoods][$loopBag]['value'];
        $maxInfo[$loopBag][$loopGoods]['goods'] = $info[$loopGoods][$loopBag]['goods'];
    }
}

foreach ($info as $good => $bagList) {
    print_r($good . '    ');
    foreach ($bagList as $weight => $bag) {
        print_r($bag['value'] . ' : ' . implode(' + ', $bag['goods']) . '    ');
    }
    print_r(PHP_EOL);
}

?>

R    0 :     0 :     1500 : R    1500 : R    1500 : R    1500 : R    1500 : R
T    0 :     0 :     1500 : R    2000 : T    2000 : T    2000 : T    3500 : T + R
H    0 :     0 :     1500 : R    2000 : T    2000 : T    3000 : H    3000 : H
B    5000 : B    5000 : B    5000 : B    6500 : B + R    7000 : B + T    7000 : B + T    8000 : B + H