一道简单的算法题

Question

比如
a物品价值1，
b物品价值2，
c物品价值8，
d物品价值10

我给出一个数字 30
求可能的组合

要求为所用到的物品最少，可重复

Answer 1

@Ukyoi_D 同学的分析很对，只是后面提出的BFS求解剪枝方法并非动态规划的常见方法，当然，方法也是正确的。

首先规范一下原题：

有n个物品，每个物品的价值为v[i],且 v[0]<=v[i]<=v[i+1]<=v[n-1];给定总价值w，求最小m个物品,使得这m个商品总价值为w.

算法是动态规划，证明过程Ukyoi_D 同学已经证明了。这里给出状态转移方程。

状态转移方程为:

 f[i][w] = min{
   f[i-1][w] if f[i-1][w] exist 
   , 
   f[i-1][w-v[i]] +1 if f[i-1][w-v[i]]exist
  }

其中f[i][w]代表在前i个物品中凑足w价值的物品需要的物品数量，f[i][w]存在表示前i个物品可以组合出w价值的物品，不存在表示不能组合出w价值的物品。

对于 f[i][w] 实际上存在3种可能，1. 选i物品，则需要物品数等于f[i-1][w-v[i]]+1。2. 不选i物品，则需要物品等于f[i-1][w], 3. f[i-1][w-v[i]]和f[i-1][w]都不存在，则f[i][w]必然也不存在。

三种情况中选出最小的，或者不存在。

具体实现上只需要一个2维数组即可，不存在的状态用无穷大表示。

Answer 2

这个应该不涉及到算法啥的，要求所用到的物品最少，那就是尽量使用价值大的物品，
用30从d-》a取整，取余，整数就是当前的要用多少个，余数是剩下的，继续往下运算，直到分配完为止

//===============================
先看一下问题：
1、没说30一定要分配完
2、要求物品最少

所以我觉得我给出解法没什么问题，勉强算贪心算法

大家都说是背包问题，我认为不是
1、背包问题是两个维度考虑，重量和价值而这里只有价值
2、背包问题要求最后价值最大化，这里仅要求物品最少

Answer 3

问题描述：

有m个物品， 价值从小到大 为V1 - Vm 
f(i) 为 "价值i且物品最少的组合"的 物品数
求解 f(n)

初始化

f(0) = 0
f(i) = +∞，1 <= i <= n

求解：

从 1到 n
f(i) = min(f(i - Vx) {1 <= x <= m && i >= Vx}) + 1 
如果不满足 1 <= x <= m && i >= Vx, f(i) = +∞

Answer 4

所用到的物品最少，可重复

那就是三个 d，刚好 30。

还有比这个更少的吗？

另外，这个根本不是背包问题啊，背包问题不仅有价值限制，还有重量限制的啊。

Answer 5

楼上说这个问题“不涉及算法”显然是不对的……这是一个多么经典的动态规划入门题……
贪心解对30这个特定的值是可行，但比如对16就是不可行的，16的最优解显然是拿两个8，而不是贪心法的先拿10再拿三个2。

原题中要用最少的物品凑够30，假如我先随便拿一个，比如我拿了一个2，接下来我还要拿28才能满足“凑够30”的要求，于是就出现了一个子问题：如何用最少物品凑够28。同理如果我拿了一个10，子问题就是我需要凑够20。

这个题目的关键在于所谓的“最优子结构”：当且仅当子问题的解是最优的，母问题的解才是最优的。举例而言，拿第一个东西我可以有1、2、8、10四种选择，于是这个问题变成四个子问题，假如我已经知道了四个子问题中的某一个的答案是这四个子问题中所拿东西最少的，就比如说需要拿k个吧，那么加上刚才拿的第一个，那么原问题就最少需要k+1个。当然实际上我们还不知道这4个子问题究竟哪个的解是最优的，所以就采用递归的方法，对四个子问题分别再求子问题，找到所有的二级子问题。在所有二级子问题之中，假如存在一个最优解，比如需要拿m个，那么同理，一级子问题的解就是至少要拿m+1个，而母问题的解就是要拿m+2个。最优子结构是动态规划实现的基础。

具体算法的实现请看 bluedream 君的解答，那个是动态规划的标准方法。我下面给出的解答用了递归，计算机需要更多资源来处理函数调用，而且通常也更慢。

---

广度优先搜索解法：

刚才的推理建立在“假如知道子问题的解”，当然二级子问题的解实际还是不知道，那就继续往下找。就这么像剥洋葱一样层层剥开（黑话叫“广度优先搜索”）。（这里有个小trick：先拿8再拿2和先拿2再拿8是一样的，优化掉后可以省一小半资源）

求到若干层之后，比如有一条路线最新的子问题要求拿满8，此时显然拿一个8就是这个子问题的最优解。那么别的路线都可以不用算了，因为别的路线最少也得再拿一个才满足要求。顺着这个找到的最优解一层一层退回去，就找到了整个问题的最优解（之一）。当然也可能某个路线最后发现无解（本题不可能，因为能拿1，总能用1凑够任何一个正整数，但如果原题目要求拿30块零5毛那么显然无解），那就舍弃这个路线，继续找其它的路线，直到找到解。或者遍历所有可能的情况发现无解。

当然上面是“广度优先”的方法，也可以用“深度优先”的方法，就是说像走迷宫一样，先顺着其中一个子问题（以及这个子问题的子问题）一条道走到黑，如果是死胡同再退回来，换一条路，这个时候找到的第一个解未必是最优解，但是有了这个解的参照，所有比这个解还要深的胡同就可以都标记成死路，不用再钻了，因为最优解的步骤比刚发现的那个肯定只少不多。如果之后又发现了更优解，就以这个更优的解作新的参照……这样钻过所有的路之后，要么一个最优解也没发现，要么最新发现的解就是最优解。

Answer 6

首先，所有手算结果的回答显然是错误的。
题主拿这个只是举个例子，实际情况当然物品价值和要求解的价值都是程序输入。
不可能手算出一个结果就说这题没意义了。

其次，上面@ekea0407 所说的贪心解法是错误的。
假设物品重量按题目说是1，2，8，10，要求解的重量是16，这个时候按贪心算法：
16=10+6=10+2+4=10+2+2+2，变成4件物品。
其实16=8+8，只需要2件物品。

最后，这个问题和背包问题还是有点区别吧，只是都用动态规划求解，求解过程也类似。
@brayden 的解法就行。
用暴力搜索遍历解空间的解法是很差的，因为暴力搜索没有把已经找到过的局部解存储下来，会多次求解同一问题。
这个题还是用动态规划合适。

Answer 7

感觉楼主这个问题几乎不涉及算法. 先用3个10,直接30了.如果有不用10的话,直接就比3个多了,问题就没有进行下去的必要了.

Answer 8

背包问题
动态规划

Answer 9

这是背包问题，上面一位同学说这个不涉及到算法，其实是不科学的。题主可以网上搜索一下楼教主的‘背包九讲’，这个问题就迎刃而解了。