这道阿三出的面试题怎么做？

阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得他超额的邮资最少？

我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，你TM的还给我写上十重循环不成？这连白板都写不下！

已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？

coin change 的变种？

【 在 UGAZ (3X天然气) 的大作中提到: 】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？

我也只会暴力破解，不过不用循环，用递归做backtracking
1. 递归函数如下： void F(vector& stamps, vector& nums, int start, int curr, vector stamps, int V, int& minDiff, vector& res)

2. 如果 curr >= V, update minDidff和 res.
3. 如果start >= nums.size(), 递归返回。

3. 继续递归：
a. 如果start所指向的邮票数不为了0,
a.1 把对应的邮票数减去1， 继续call递归
a.2 不使用start对应的邮票，把start +1， 继续call递归。
b. 如果start所指向的邮票用完了，start+1， 继续call递归。

【 在 UGAZ (3X天然气) 的大作中提到: 】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？

这难道不是多重背包问题吗?
【 在 UGAZ (3X天然气) 的大作中提到: 】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？

Subset Sum?

碰到这种变态题应该离开甩脸走人。面试题一般是准备了的就能做，没准备过的就做不出，就这么简单。

【 在 UGAZ (3X天然气) 的大作中提到: 】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？

只能用DFS + memorize了吧。每个state记录的是能不能用n1, n2, n3 凑成价值为V的
投资，往前递归到 (n1-1, n2, n3, V-c1), (n1, n2-1,....这样。最后计算V到V+max(c1, c2, c3)中间的值取最小。complexity是n1*n2*n3*V

【 在 UGAZ (3X天然气) 的大作中提到: 】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？

显然是用中国剩余定理啊
参加过数学竞赛的应该都知道

这是个好办法。也比较好想
【 在 wwrechard (木有...) 的大作中提到: 】
: 只能用DFS + memorize了吧。每个state记录的是能不能用n1, n2, n3 凑成价值为V的
: 投资，往前递归到 (n1-1, n2, n3, V-c1), (n1, n2-1,....这样。最后计算V到V+
max(
: c1, c2, c3)中间的值取最小。complexity是n1*n2*n3*V

你们专业马工就这水平？我一个生物苦逼数据处理员都知道应该用dynamic
programming

全是泡沫啊

就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最少coin
个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin比较一
下就知道取哪个了。

就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最少coin
个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin比较一
下就知道取哪个了。

题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是要求最
后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足总价为v的最少邮票数。

【 在 Jun0214(ajun) 的大作中提到: 】

: 就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最
少coin

: 个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin
比较一

: 下就知道取哪个了。

这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取哪个coin不就行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟取的是哪个
coin就是，这个信息一并记录在每一步里而已

【 在 dullview(dullview) 的大作中提到: 】

: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是
要求最

: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足总价为

: v的最少邮票数。

: 少coin

: 比较一

就是相当于原题添加一个问题，就是如果有最小值，把最小值的构成给出。解法就是每一步比较记录下取的是哪个coin

【 在 Jun0214(ajun) 的大作中提到: 】

: 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取哪个
coin不就

: 行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟取的是
哪个

: coin就是，这个信息一并记录在每一步里而已

: 要求最

: 总价为

说了题目要求不是使得邮票数最少，是邮票总价值能寄邮费V的东西，你要使这个总价
最小。也就说说你要尽可能找出个答案能能凑出V，如果不能凑出V 1,V 2。不清楚你的
方法怎么work.

【 在 Jun0214(ajun) 的大作中提到: 】
<br>: 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取哪个
coin不就
<br>: 行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟
取的是
哪个
<br>: coin就是，这个信息一并记录在每一步里而已
<br>: 要求最
<br>: 总价为
<br>

我这个即是最少邮票数，也是最少花费啊。上个的n值是刚好，根据v减n的差，选择最
后一个邮票构成最少花费

【 在 dullview(dullview) 的大作中提到: 】

: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是
要求最

: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足总价为

: v的最少邮票数。

: 少coin

: 比较一

不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是在dp[V]
没解的情况下，接下
去算dp[V+1], dp[V+2]， 直到算出第一个dp[j]有解并且j>=V结束？ 考虑到这题要求
给出具体邮票组合，所以递归加memorization不就好了么。

【 在 Jun0214 (ajun) 的大作中提到: 】
: 我这个即是最少邮票数，也是最少花费啊。上个的n值是刚好，根据v减n的差，选择最
: 后一个邮票构成最少花费
:
: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是
: 要求最
:
: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足
: 总价为
:
: v的最少邮票数。
:
: 少coin
:
: 比较一
:

Sort c1, c2, c3
Then assume c1Ceil((V-floor(v/ c3) *c3 - floor((v- floor/c3)/c2) * c2)/c1)

先用大额的邮票，再用小额的邮票， 最后用最小额的邮票。

要考虑几种特殊情况，用某一额度的邮票刚好付完。
或者某一额度股票很少的情况， 比如 n3 小于 floor(v/c3)

还有比如， v比c3小，或者v比c2小等等特别情况
比较全用大额服完，用大额和小额付完， 大额小额叫最小额付完
【 在 thinkingwate (HUYOU) 的大作中提到: 】
: Sort c1, c2, c3
: Then assume c1

complex 不一样，DP 快多了。

【 在 dullview (dullview) 的大作中提到: 】
: 不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是在dp[V]
: 没解的情况下，接下
: 去算dp[V+1], dp[V+2]， 直到算出第一个dp[j]有解并且j>=V结束？ 考虑到这题要求
: 给出具体邮票组合，所以递归加memorization不就好了么。

靠，这是我出过的面试题，被看了被某个被我面试过的偷走了。。。看了你们这些高薪码农回答，唉，，，如今真是泡沫时代啊

就一背包问题

这是不是就是上楼说的剩余定理。 好想是比较好的解法。

【 在 thinkingwate (HUYOU) 的大作中提到: 】
: Sort c1, c2, c3
: Then assume c1: Ceil((V-floor(v/ c3) *c3 - floor((v- floor/c3)/c2) * c2)/c1)
: 先用大额的邮票，再用小额的邮票， 最后用最小额的邮票。
: 要考虑几种特殊情况，用某一额度的邮票刚好付完。
: 或者某一额度股票很少的情况， 比如 n3 小于 floor(v/c3)

【 在 huhu1 (呼呼~) 的大作中提到: 】
: coin change 的变种？

我觉得这个是正解~~~

专业解法： linear programming
Obj: min(x1*c1+x1 *c2+x3*c3)
X1*c1+x2*c2+x3*c3>= v
0<=x1<=n1
0<=x2<=n2
0<=x3<=n3
都有现成的算法

正解，最少邮资，而不是最少个数

【 在 thinkingwate(HUYOU) 的大作中提到: 】

: 专业解法： linear programming

: Obj: min(x1*c1 x1 *c2 x3*c3)

: X1*c1 x2*c2 x3*c3

大家都只是看一眼，给个想法。明明就有好几个很有效的方法，被你嘲笑高薪码农会个啥。这种是我最讨厌的面试官。跟你说给你出个简单问题，然后出个hard的题目给你。一副你知道解法吗，等别人给了一个不一样的解法又是你这傻逼知道啥的态度，然后在各种细节上试图fail你。不了解自己的问题，不是带着考察别人解决问题和coding的能力去面试的。

【 在 cheart(heart) 的大作中提到: 】

: 靠，这是我出过的面试题，被看了被某个被我面试过的偷走了。。。看了你们这些高薪

: 码农回答，唉，，，如今真是泡沫时代啊

看了大家的讨论，觉得多重背包应该是正解。虽然我一直没准备过背包问题，也很怕DP的说。

令U = c1*n1 + c2*n2 + c3*n3 - V
则原题可以转换为多重背包问题：
背包的最大承重为U,物品的重量和价值都设成邮票的面值，这样就可以参考背包九讲用DP求出结果。

那些没放入背包的邮票就是原题的解答。

DP解决吧
首先题目说了邮票总额W=c1*n1+c2*n2+c3*n3是大于V的，那么考虑boolean dp[W+1],其中dp[k]=true表示总数k能够被组合出来，从dp[V]开始检验增加到dp[W],第一个为true的时候就停止。
bottom-up的过程是dp[k]= (dp[k-c1] || dp[k-c2] || dp[k-c3])
复杂度应该是 O(W) (从dp[1]算到dp[W])

其实没那么直观的，貌似题目限制了每种邮票的个数。所以，你这个递推是会有问题的。

【 在 NickelOleGen(五美分) 的大作中提到: 】

: DP解决吧

: 首先题目说了邮票总额W=c1*n1 c2*n2 c3*n3是大于V的，那么考虑boolean dp[W 1],其

: 中dp[k]=true表示总数k能够被组合出来，从dp[V]开始检验增加到dp[W],第一个为true

: 的时候就停止。

: bottom-up的过程是dp[k]= (dp[k-c1] || dp[k-c2] || dp[k-c3])

: 复杂度应该是 O(W) (从dp[1]算到dp[W])

不用这样的。可能的解在V和V C之间。C是最大面额的邮票。你直接用v C定义多重背包公式dp数组。在这个范围内算应该就可以了。

【 在 NickelOleGen(五美分) 的大作中提到: 】

: DP解决吧

: 首先题目说了邮票总额W=c1*n1 c2*n2 c3*n3是大于V的，那么考虑boolean dp[W 1],其

: 中dp[k]=true表示总数k能够被组合出来，从dp[V]开始检验增加到dp[W],第一个为true

: 的时候就停止。

: bottom-up的过程是dp[k]= (dp[k-c1] || dp[k-c2] || dp[k-c3])

: 复杂度应该是 O(W) (从dp[1]算到dp[W])

背包 O(v * N）N = sum of ni

【在 UGAZ(3X天然气)的大作中提到：】
：阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
：要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。

典型背包问题，每张邮票为0（没选中）或1（选中）
扩展问题到n张邮票，总邮资为v, 设定一个可能的解为上限，比如Z=sum(c[0]..c[k]) > v

定义dp[i][j] = 0 或 1， 为c[0]..c[i]是否可以组成和为j, j = 0 .. Z
dp[i+1][j] = dp[i][j] | dp[i][j-c[i]]

然后找dp[n-1][v] 到 dp[n-1][Z]之间第一个为1的，比如dp[n-1][k]
然后从dp[n-1][k]反推回去，找到一组解，解不止一个
复杂度为O(Z*n)

vector minStamps(int c1, int n1, int c2, int n2, int c3, int n3, int v) {
vector res;
vector stamps(n1, c1);
vector temp1(n2, c2);
vector temp2(n3, c3);

stamps.insert(stamps.end(), temp1.begin(), temp1.end());
stamps.insert(stamps.end(), temp2.begin(), temp2.end());

int Z = 0;
int n = n1 + n2 + n3;

if (v == 0) return res;

for (int i = 0; i < stamps.size(); i++)
{
Z += stamps[i];
if (Z == v)
{
stamps.resize(i + 1);
return stamps;
}
else if (Z > v)
break;
}

vector> dp(n, vector(Z + 1, 0));

for (int i = 0; i < n; i++)
dp[i][0] = 1;

for (int j = 1; j < Z + 1; j++)
{
if (stamps[0] == j)
dp[0][j] = 1;
}

for (int i = 1; i < n; i++)
{
for (int j = 1; j < Z + 1; j++)
{
dp[i][j] = dp[i - 1][j];
if (j - stamps[i] >= 0)
{
dp[i][j] = dp[i][j] | dp[i - 1][j - stamps[i]];
}
}
}

int k = v;
while (k <= Z && dp[n - 1][k] == 0)
k++;

if (k > Z) return res;

int j = n - 1;
while (j >= 0)
{
while (j >= 0 && dp[j][k] == 1)
j--;

res.push_back(stamps[j + 1]);
k = k - stamps[j + 1];
}

return res;

}

可以把邮票数组打了平了变成c1,c1,c2,c2,c3,c3,c4,c4,c4，你的那个修改下应该是可以work的

【 在 Jun0214(ajun) 的大作中提到: 】

: 我弄错了，没考虑邮票数量的限制. 我这个只适用于假设各种邮票数量足够的情况

不是，这题目也就国内高中竞赛中级水平 你们一帮大厂资深程序员就这水平？

你这么说有点过了。别跟我提国内那种超纲超前填鸭式装逼竞赛。在这讨论的也不像是大厂资深程序员，估计大部分都是新手甚至转行的。

【 在 ashcroft(meiyou) 的大作中提到: 】

: 不是，这题目也就国内高中竞赛中级水平 你们一帮大厂资深程序员就这水平？

一个题目如果别人没做过，需要一点时间想，整理思路，不都是很正常的事情么。就算刷了几百道题进到现在热门大厂的人，找出一个没见过的题，又几个又敢拍胸脯说自己绝对能做出来么。面试遇到这样的面试官，那就只能败了。

【 在 HarvardThief (博后肄业) 的大作中提到: 】
: 你这么说有点过了。别跟我提国内那种超纲超前填鸭式装逼竞赛。在这讨论的也不像是
: 大厂资深程序员，估计大部分都是新手甚至转行的。
:
: 不是，这题目也就国内高中竞赛中级水平 你们一帮大厂资深程序员就这水平？
: