一个最优化问题

[qinjiannet]

观察下面的表格

   B1 B2 B3 B4
A1 9  9  8  3   10
A2 2  6  4  4   40
A3 8  9  3  4   30
A4 3  3  5  2   60
A5 9  9  1  6   90
   50 60 50 70
	

---

上表中 A1~A5 表示 5 家快递公司， B1~B4 表示 4 种商品，矩阵内的值表示快递公司运送某种商品的单价。

矩阵右侧的值表示各家快递公司需要运送的商品总数

矩阵下方的值表示每种商品的总数

求满足上述约束条件的最小运费

[liuzhster]

多重背包问题?

[goodryb]

下表不是从 0 开始，差评

[Kilerd]

感觉楼上说对了，可以试试。 这种就是背包模型嘛。

[q397064399]

动态规划题，╮(╯▽╰)╭ 先把递归公式写出来吧，写出来就差不多了

[q397064399]

个人建议 不会背包 或者 背包不熟悉 ，这种题目 直接给它穷举就好了

[ArieShout]

前面几位回答就像数学答案上面的“易得”，“显然”一样呃

[justyy]

个人感觉应该是动态规化，可是我写不出来公式。。有大牛教教 我么？
如果 A 只有 5 个， B 只有 4 个， 完全可以暴力。

[qinjiannet]

@q397064399 这个问题穷举的复杂度是多少？

[wodesuck]

为什么这么多人说是背包？
我觉得是个费用流啊。
求背包状态转移方程。

[billgreen1]

如果商品是整数，那么是整数规划问题，有现成的软件包的

[q397064399]

@qinjiannet 排列组合就好，自己算吧

[q397064399]

@ArieShout
不是显然，或者易得， 刷 OJ 的人 大多都会临时突击 各种算法 ，
目的是啥，不还是套路，既然出了这个题目，就证明这个问题是计算可行性的，那不就是套路了，
万千世界，其实就一个套路 就可以解释，万物所有的规律 包括 牛顿定律 啥的 都是套路，
这题就算不是 DP 也跟 DP 差的八九不离十，

[q397064399]

@qinjiannet

但是穷举有一个问题，要排除无效集
穷举的思路 是针对限定条件的，例如

B1 B2 B3 B4
A1 9 9 8 3 10
A2 2 6 4 4 40
A3 8 9 3 4 30
A4 3 3 5 2 60
A5 9 9 1 6 90
50 60 50 70

这里 10 40 30 60 90 就是一个限定条件，

显然可以通过枚举计算出 10 40 30 60 90 ，分别 由 4 个整数组成的 排列组合，

这样就枚举出来 所有 A1 快递公司所能 运送 4 种商品的 条件集合

快递公司的运送不同商品的结果集计算复杂度 O(n4)

貌似还有更优的算法，不过我了解过（如果有知道的 可以告知我一声）

A1 计算次数是 （ 10 ） 4 次方
A2 计算次数是 （ 40 ） 4 次方
..
A5 的计算次数是（ 90 ） 4 次方

依次下来 通过过滤
就能得到所有快递公司 运送这 4 种商品的可行性集合，
（但是这个可行性集 并不满足货物数量的限定条件）

然后再从这个集合中，找出 符合（ 50 60 50 70 ）的集合


最终从这个合法的集合当中 排序获得最大值即可

[q397064399]

@wodesuck
这个问题 其实只要上过高中就能解，但是通过限定条件穷举出 合法集，是一种非常傻逼的行为，
在会算法的程序员来看（我真不会多少算法），这种方法有点 Low 假如问题规模变大了，几乎是很难解的出来

[q397064399]

DP 的思想 其实就是通过转移方程，将一些不必要的计算结果集 给排除掉了

[q397064399]

再次强调，通过 X Y 的限定条件来穷举合法矩阵集的最优解 是非常 Low 的行为，

如果有 人知道此类问题的算法叫什么名字 麻烦请告知我一声，（除了 DP ）

[Xs0ul]

看起来像是线性规划（

[zouxy]

好像叫 单纯形法

[zouxy]

华罗庚主持编写那本绿色封面 运筹学 上有

[BBrother]

有种运筹学作业的既视感