U**Z
发帖数: 80 | 1 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
他超额的邮资最少？
我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
你TM的还给我写上十重循环不成？这连白板都写不下！
已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？ |
h***1
发帖数: 2263 | 2 coin change 的变种？
【在 U**Z 的大作中提到】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？
|
d******w
发帖数: 2213 | 3 我也只会暴力破解，不过不用循环，用递归做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递归。
【在 U**Z 的大作中提到】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？
|
m*******u
发帖数: 13 | 4 这难道不是多重背包问题吗?
【在 U**Z 的大作中提到】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？
|
D***n
发帖数: 149 | |
c*********l
发帖数: 926 | 6 碰到这种变态题应该离开甩脸走人。面试题一般是准备了的就能做，没准备过的就做不
出，就这么简单。
【在 U**Z 的大作中提到】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？
|
w*******d
发帖数: 59 | 7 只能用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
【在 U**Z 的大作中提到】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？
|
n******r
发帖数: 718 | 8 显然是用中国剩余定理啊
参加过数学竞赛的应该都知道 |
d******w
发帖数: 2213 | 9 这是个好办法。也比较好想
max(
【在 w*******d 的大作中提到】
: 只能用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
|
H**********f
发帖数: 2978 | 10 你们专业马工就这水平？我一个生物苦逼数据处理员都知道应该用dynamic
programming
全是泡沫啊 |
|
|
J*****4
发帖数: 1 | 11 就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最少coin
个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin比较一
下就知道取哪个了。 |
J*****4
发帖数: 1 | 12 就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最少coin
个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin比较一
下就知道取哪个了。 |
d******w
发帖数: 2213 | 13 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是要求最
后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足总价为
v的最少邮票数。
: 就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最
少coin
: 个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin
比较一
: 下就知道取哪个了。
【在 J*****4 的大作中提到】
: 就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最少coin
: 个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin比较一
: 下就知道取哪个了。
|
J*****4
发帖数: 1 | 14 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取哪个coin不就
行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟取的是哪个
coin就是，这个信息一并记录在每一步里而已
: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是
要求最
: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足
总价为
: v的最少邮票数。
: 少coin
: 比较一
【在 d******w 的大作中提到】
: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是要求最
: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足总价为
: v的最少邮票数。
:
:
: 就coin change的dynamic变种。多记录下最后一个可以分解的数字n. 取v的最
: 少coin
:
: 个数。如果取到则为刚好。如果取不到，v减上次可分解值n 的差值与三个coin
: 比较一
:
: 下就知道取哪个了。
:
|
J*****4
发帖数: 1 | 15 就是相当于原题添加一个问题，就是如果有最小值，把最小值的构成给出。解法就是每
一步比较记录下取的是哪个coin
: 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取哪个
coin不就
: 行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟取的是
哪个
: coin就是，这个信息一并记录在每一步里而已
: 要求最
: 总价为
【在 J*****4 的大作中提到】
: 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取哪个coin不就
: 行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟取的是哪个
: coin就是，这个信息一并记录在每一步里而已
:
:
: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是
: 要求最
:
: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足
: 总价为
:
: v的最少邮票数。
:
: 少coin
|
d******w
发帖数: 2213 | 16 说了题目要求不是使得邮票数最少，是邮票总价值能寄邮费V的东西，你要使这个总价
最小。也就说说你要尽可能找出个答案能能凑出V，如果不能凑出V 1,V 2。不清楚你的
方法怎么work.
: 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取
哪个
coin不就
: 行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟
取的是
哪个
: coin就是，这个信息一并记录在每一步里而已
: 要求最
: 总价为
【在 J*****4 的大作中提到】
: 就是相当于原题添加一个问题，就是如果有最小值，把最小值的构成给出。解法就是每
: 一步比较记录下取的是哪个coin
:
:
: 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取哪个
: coin不就
:
: 行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟取的是
: 哪个
:
: coin就是，这个信息一并记录在每一步里而已
:
: 要求最
:
: 总价为
|
J*****4
发帖数: 1 | 17 我这个即是最少邮票数，也是最少花费啊。上个的n值是刚好，根据v减n的差，选择最
后一个邮票构成最少花费
: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是
要求最
: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足
总价为
: v的最少邮票数。
: 少coin
: 比较一
【在 d******w 的大作中提到】
: 说了题目要求不是使得邮票数最少，是邮票总价值能寄邮费V的东西，你要使这个总价
: 最小。也就说说你要尽可能找出个答案能能凑出V，如果不能凑出V 1,V 2。不清楚你的
: 方法怎么work.
:
:
: 这个有什么难的，前面每次比较取哪个coin才使数字最小的时候记录下取
: 哪个
: coin不就
:
: 行了。原来直接min. 现在需要修改下那个比较流程，以记录每一步究竟
: 取的是
: 哪个
|
d******w
发帖数: 2213 | 18 不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是在dp[V]
没解的情况下，接下
去算dp[V+1], dp[V+2]， 直到算出第一个dp[j]有解并且j>=V结束？ 考虑到这题要求
给出具体邮票组合，所以递归加memorization不就好了么。
【在 J*****4 的大作中提到】
: 我这个即是最少邮票数，也是最少花费啊。上个的n值是刚好，根据v减n的差，选择最
: 后一个邮票构成最少花费
:
:
: 题目是说寄这件东西总价V，你的邮可能能奏起V， 不然你就要多贴邮票。它是
: 要求最
:
: 后你贴的邮票总价值最小，然后给出这个最小总价值下有那些贴法。而不是满足
: 总价为
:
: v的最少邮票数。
:
: 少coin
:
: 比较一
|
t**********e
发帖数: 134 | 19 Sort c1, c2, c3
Then assume c1
Ceil((V-floor(v/ c3) *c3 - floor((v- floor/c3)/c2) * c2)/c1)
先用大额的邮票，再用小额的邮票， 最后用最小额的邮票。
要考虑几种特殊情况，用某一额度的邮票刚好付完。
或者某一额度股票很少的情况， 比如 n3 小于 floor(v/c3) |
t**********e
发帖数: 134 | 20 还有比如， v比c3小，或者v比c2小等等特别情况
【在 t**********e 的大作中提到】
: Sort c1, c2, c3
: Then assume c1: Ceil((V-floor(v/ c3) *c3 - floor((v- floor/c3)/c2) * c2)/c1)
: 先用大额的邮票，再用小额的邮票， 最后用最小额的邮票。
: 要考虑几种特殊情况，用某一额度的邮票刚好付完。
: 或者某一额度股票很少的情况， 比如 n3 小于 floor(v/c3)
|
|
|
h***1
发帖数: 2263 | 21 complex 不一样，DP 快多了。
[V]
【在 d******w 的大作中提到】
: 不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是在dp[V]
: 没解的情况下，接下
: 去算dp[V+1], dp[V+2]， 直到算出第一个dp[j]有解并且j>=V结束？ 考虑到这题要求
: 给出具体邮票组合，所以递归加memorization不就好了么。
|
c****t
发帖数: 220 | 22 靠，这是我出过的面试题，被看了被某个被我面试过的偷走了。。。看了你们这些高薪
码农回答，唉，，，如今真是泡沫时代啊 |
r*******y
发帖数: 270 | |
E**********e
发帖数: 1736 | 24 这是不是就是上楼说的剩余定理。 好想是比较好的解法。
【在 t**********e 的大作中提到】
: Sort c1, c2, c3
: Then assume c1: Ceil((V-floor(v/ c3) *c3 - floor((v- floor/c3)/c2) * c2)/c1)
: 先用大额的邮票，再用小额的邮票， 最后用最小额的邮票。
: 要考虑几种特殊情况，用某一额度的邮票刚好付完。
: 或者某一额度股票很少的情况， 比如 n3 小于 floor(v/c3)
|
q*****t
发帖数: 81 | 25
我觉得这个是正解~~~
【在 h***1 的大作中提到】
: coin change 的变种？
|
t**********e
发帖数: 134 | 26 专业解法： 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
都有现成的算法 |
n**********2
发帖数: 1 | 27 正解，最少邮资，而不是最少个数
: 专业解法： linear programming
: Obj: min(x1*c1 x1 *c2 x3*c3)
: X1*c1 x2*c2 x3*c3
【在 t**********e 的大作中提到】
: 专业解法： 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
: 都有现成的算法
|
y*******2
发帖数: 1 | 28 大家都只是看一眼，给个想法。明明就有好几个很有效的方法，被你嘲笑高薪码农会个
啥。这种是我最讨厌的面试官。跟你说给你出个简单问题，然后出个hard的题目给你。
一副你知道解法吗，等别人给了一个不一样的解法又是你这傻逼知道啥的态度，然后在
各种细节上试图fail你。不了解自己的问题，不是带着考察别人解决问题和coding的能
力去面试的。
: 靠，这是我出过的面试题，被看了被某个被我面试过的偷走了。。。看了你们这
些高薪
: 码农回答，唉，，，如今真是泡沫时代啊
【在 c****t 的大作中提到】
: 靠，这是我出过的面试题，被看了被某个被我面试过的偷走了。。。看了你们这些高薪
: 码农回答，唉，，，如今真是泡沫时代啊
|
U**Z
发帖数: 80 | 29 看了大家的讨论，觉得多重背包应该是正解。虽然我一直没准备过背包问题，也很怕DP
的说。
令U = c1*n1 + c2*n2 + c3*n3 - V
则原题可以转换为多重背包问题：
背包的最大承重为U,物品的重量和价值都设成邮票的面值，这样就可以参考背包九讲用
DP求出结果。
那些没放入背包的邮票就是原题的解答。 |
N**********n
发帖数: 1 | 30 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]) |
|
|
y*******2
发帖数: 1 | 31 其实没那么直观的，貌似题目限制了每种邮票的个数。所以，你这个递推是会有问题的。
: 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])
【在 N**********n 的大作中提到】
: 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])
|
y*******2
发帖数: 1 | 32 不用这样的。可能的解在V和V C之间。C是最大面额的邮票。你直接用v C定义多重背包
公式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])
【在 N**********n 的大作中提到】
: 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])
|
c**s
发帖数: 159 | 33 背包 O(v * N）N = sum of ni
：阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
：要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。 |
s*******r
发帖数: 31 | 34 典型背包问题，每张邮票为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;
} |
J*****4
发帖数: 1 | 35 不嘴炮了，直接上码：python
def coinChange(self, tickets, v: int) -> int:
minindex = 0
minvalue = tickets[0]
maxvalue= tickets[0]
for j, c in enumerate(tickets):
if c < minvalue:
minvalue=c
minindex = j
if c> maxvalue:
maxvalue=c
dp = [math.inf] * (v + 1 + maxvalue)
dp[0] = 0
dp2 = [] # detail
detail0=[0]*len(tickets)
dp2.append(detail0)
pre_n=0
next_n=0
for i in range(1, v + 1 + maxvalue ):
selected= -1
for j,c in enumerate(tickets):
if c <= i:
if dp[i - c] + 1
selected=j
dp[i] =dp[i - c] + 1
if selected==-1:
dp2.append(None)
else:
pre= copy.deepcopy(dp2[i-tickets[selected]])
pre[selected]=pre[selected]+1
dp2.append(pre)
if i>v:
next_n=i
break
pre_n=i
if dp[v] == math.inf:
if pre_n+minvalue
pre = copy.deepcopy(dp2[pre_n])
pre[minindex] = pre[minindex] + 1
return pre
else:
return dp2[next_n]
else:
return dp2[v]
[V]
【在 d******w 的大作中提到】
: 不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是在dp[V]
: 没解的情况下，接下
: 去算dp[V+1], dp[V+2]， 直到算出第一个dp[j]有解并且j>=V结束？ 考虑到这题要求
: 给出具体邮票组合，所以递归加memorization不就好了么。
|
J*****4
发帖数: 1 | 36 你说的是对的啊，如果v无解，找到连续有解的值i和j，i
然后i值加上最小的那个邮票值，与j比较。取小的那个
: 不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是
在dp[V]
: 没解的情况下，接下
: 去算dp[V 1], dp[V 2]， 直到算出第一个dp[j]有解并且j
【在 d******w 的大作中提到】
: 不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是在dp[V]
: 没解的情况下，接下
: 去算dp[V+1], dp[V+2]， 直到算出第一个dp[j]有解并且j>=V结束？ 考虑到这题要求
: 给出具体邮票组合，所以递归加memorization不就好了么。
|
N**********n
发帖数: 1 | 37 嗯，你说的对，我考虑的是无限个数，每种邮票现在个数有限就不能这么做了
的。
[W
【在 y*******2 的大作中提到】
: 其实没那么直观的，貌似题目限制了每种邮票的个数。所以，你这个递推是会有问题的。
:
:
: 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])
|
y*******2
发帖数: 1 | 38 或者把邮票摊开来，变成c1,c1, c2,c2,c2, c3,c3,c3，其实就是把多重背包转换成0/1
背包。这样应该就可以用你的公式了。
【在 N**********n 的大作中提到】
: 嗯，你说的对，我考虑的是无限个数，每种邮票现在个数有限就不能这么做了
:
: 的。
: [W
|
N**********n
发帖数: 1 | 39 对，刚才下面那个sandboxer的帖子就是这样的
/1
【在 y*******2 的大作中提到】
: 或者把邮票摊开来，变成c1,c1, c2,c2,c2, c3,c3,c3，其实就是把多重背包转换成0/1
: 背包。这样应该就可以用你的公式了。
|
d******b
发帖数: 73 | 40 直接说，10个，我就粘贴10遍。如果有20种邮票，你面完我估计程序还没有跑完。 |
|
|
J*****4
发帖数: 1 | 41 我弄错了，没考虑邮票数量的限制. 我这个只适用于假设各种邮票数量足够的情况
: 不嘴炮了，直接上码：python
: def coinChange(self, tickets, v: int) -
【在 J*****4 的大作中提到】
: 你说的是对的啊，如果v无解，找到连续有解的值i和j，i: 然后i值加上最小的那个邮票值，与j比较。取小的那个
:
:
: 不太懂根据v减n的差来计算那步。假设dp[i]表示总额为i 时的min邮票数，不是
: 在dp[V]
:
: 没解的情况下，接下
:
: 去算dp[V 1], dp[V 2]， 直到算出第一个dp[j]有解并且j
|
y*******2
发帖数: 1 | 42 可以把邮票数组打了平了变成c1,c1,c2,c2,c3,c3,c4,c4,c4，你的那个修改下应该是可
以work的
: 我弄错了，没考虑邮票数量的限制. 我这个只适用于假设各种邮票数量足够的情况
【在 J*****4 的大作中提到】
: 我弄错了，没考虑邮票数量的限制. 我这个只适用于假设各种邮票数量足够的情况
:
:
: 不嘴炮了，直接上码：python
:
: def coinChange(self, tickets, v: int) -
|
a******t
发帖数: 72 | 43 不是，这题目也就国内高中竞赛中级水平 你们一帮大厂资深程序员就这水平？ |
H**********f
发帖数: 2978 | 44 你这么说有点过了。别跟我提国内那种超纲超前填鸭式装逼竞赛。在这讨论的也不像是
大厂资深程序员，估计大部分都是新手甚至转行的。
: 不是，这题目也就国内高中竞赛中级水平 你们一帮大厂资深程序员就这水平？
【在 a******t 的大作中提到】
: 不是，这题目也就国内高中竞赛中级水平 你们一帮大厂资深程序员就这水平？
|
d******w
发帖数: 2213 | 45 一个题目如果别人没做过，需要一点时间想，整理思路，不都是很正常的事情么。就算
刷了几百道题进到现在热门大厂的人，找出一个没见过的题，又几个又敢拍胸脯说自己
绝对能做出来么。面试遇到这样的面试官，那就只能败了。
【在 H**********f 的大作中提到】
: 你这么说有点过了。别跟我提国内那种超纲超前填鸭式装逼竞赛。在这讨论的也不像是
: 大厂资深程序员，估计大部分都是新手甚至转行的。
:
:
: 不是，这题目也就国内高中竞赛中级水平 你们一帮大厂资深程序员就这水平？
:
|
P**H
发帖数: 1897 | 46 这是ILP。算法有。但是这里情况只有3阶。可以用dp。好像是O(V^3)。
#include
#include
#include
#include
#include
using namespace std;
int overpaid(int v, vector &c, vector &n,
unordered_map &min_map);
int main() {
cout << "Hello World"
<< "n";
unordered_map min_map;
int c_ints[] = {53, 23, 43};
vector c(c_ints, c_ints + sizeof(c_ints) / sizeof(int));
int n_ints[] = {1000, 1000, 1000};
vector n(n_ints, n_ints + sizeof(n_ints) / sizeof(int));
cout << to_string(overpaid(1000, c, n, min_map)) << "n";
return 0;
}
int overpaid(int v, vector &c, vector &n,
unordered_map &min_map) {
string key;
for (int i = 0; i < c.size(); ++i) {
key += to_string(n[i]) + ".";
}
if (min_map.find(key) != min_map.end()) {
return min_map.at(key);
}
vector min_values;
for (int i = 0; i < c.size(); ++i) {
if (n[i] < 1) {
min_values.push_back(1000);
} else if (v < c[i]) {
min_values.push_back(c[i] - v);
} else {
vector n_next = n;
n_next[i] -= 1;
min_values.push_back(overpaid(v - c[i], c, n_next, min_map));
}
}
int min_value = min(min_values[0], min(min_values[1], min_values[2]));
min_map.insert({{key, min_value}});
return min_value;
}
【在 t**********e 的大作中提到】
: 专业解法： 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
: 都有现成的算法
|
w*******d
发帖数: 59 | 47 贪心法明显不对。我的邮票面值是3, 5需要凑4正确解是一张5，你的解法要两张3
【在 t**********e 的大作中提到】
: Sort c1, c2, c3
: Then assume c1: Ceil((V-floor(v/ c3) *c3 - floor((v- floor/c3)/c2) * c2)/c1)
: 先用大额的邮票，再用小额的邮票， 最后用最小额的邮票。
: 要考虑几种特殊情况，用某一额度的邮票刚好付完。
: 或者某一额度股票很少的情况， 比如 n3 小于 floor(v/c3)
|
w*******d
发帖数: 59 | 48 你理解的DP就只有bottom-up的吗。。。递归+memorization就是top-down DP
【在 h***1 的大作中提到】
: complex 不一样，DP 快多了。
:
: [V]
|
w*******d
发帖数: 59 | 49 解不是整数怎么办？Rounding吗？怎么证明rounding之后还是最优解？
【在 t**********e 的大作中提到】
: 专业解法： 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
: 都有现成的算法
|
l******r
发帖数: 1 | 50 这个应该用linear programming。
simplex algorithm
【在 U**Z 的大作中提到】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？
|
|
|
t**********e
发帖数: 134 | 51 Google
【在 w*******d 的大作中提到】
: 解不是整数怎么办？Rounding吗？怎么证明rounding之后还是最优解？
|
h*********d
发帖数: 336 | 52 贴个Java code。
public static int stampSum(int[] stamps, int[] count, int V) {
int N = 0;
for (int i=0; i
int[] A = new int[N];
int idx = 0;
for (int i=0; i
for (int j=0; j
A[idx++] = stamps[i];
}
}
return dfs(A,0, V, 0);
}
private static int dfs(int[] A, int sum, int V, int startIdx) {
if (sum >= V) return sum-V;
int min = Integer.MAX_VALUE;
for (int i=startIdx; i
int diff = dfs(A, sum + A[i], V, i+1);
min = Math.min(min, diff);
if (min == 0) return min;
}
return min;
}
【在 U**Z 的大作中提到】
: 阿三手头有三种面值分别为c1, c2和c3的邮票，数量分别为n1, n2和n3。
: 要邮寄一个包裹，所需邮资为V(假定不超过阿三手头邮票面值总额）。
: 注意到阿三未必能凑出总面值恰好为的邮票，请问阿三应该如何给包裹贴上邮票，使得
: 他超额的邮资最少？
: 我用了三重循环的暴力求解，结果被阿三鄙视了。他说如果问题改为十种面值的邮票，
: 你TM的还给我写上十重循环不成？这连白板都写不下！
: 已跪。尼玛，对付这样的NPC问题，正解是什么？是不是leetcode原题？
|
