Redian新闻
>
求解比硬币找零稍难的一题
avatar
求解比硬币找零稍难的一题# JobHunting - 待字闺中
j*l
1
我想这题和背包一样是NP的,不知道是否是要用动态规划来解?
有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在
要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。
N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。
avatar
s*y
2
what do you mean 尽可能的小?

【在 j**l 的大作中提到】
: 我想这题和背包一样是NP的,不知道是否是要用动态规划来解?
: 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在
: 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。
: N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。

avatar
j*l
3
必须perfect pay,或者over pay, 不能under pay,
但又想over pay的尽可能少,如果不能perfect pay的话
举个例子就知道了。
比如面值为2分,5分,8分,10分,12分的邮票各一张,邮资是16分,
就选2分,5分,10分,或者选5分,12分,都是over pay了1分。

【在 s*****y 的大作中提到】
: what do you mean 尽可能的小?
avatar
g*s
4
in this case i think 5 + 12 is better.

【在 j**l 的大作中提到】
: 必须perfect pay,或者over pay, 不能under pay,
: 但又想over pay的尽可能少,如果不能perfect pay的话
: 举个例子就知道了。
: 比如面值为2分,5分,8分,10分,12分的邮票各一张,邮资是16分,
: 就选2分,5分,10分,或者选5分,12分,都是over pay了1分。

avatar
r*k
5
子最有解不好转换成当前最优解啊。。。
avatar
o*p
6
No, it is impossible to solve this problem by dynamic programming because
this problem doesn't exhibit optimal substructure.
For example, postage of 8 cents is a subprogram of postage of 16 cents. But
the optimal solution for 8 cents is just one 8 cents stamp, which is not
part of the optimal solution for postage of 16 cents.
I guess this problem is NPC.

【在 j**l 的大作中提到】
: 必须perfect pay,或者over pay, 不能under pay,
: 但又想over pay的尽可能少,如果不能perfect pay的话
: 举个例子就知道了。
: 比如面值为2分,5分,8分,10分,12分的邮票各一张,邮资是16分,
: 就选2分,5分,10分,或者选5分,12分,都是over pay了1分。

avatar
s*y
7
Agree. Seems not fulfill the requirement of DP.

But

【在 o*******p 的大作中提到】
: No, it is impossible to solve this problem by dynamic programming because
: this problem doesn't exhibit optimal substructure.
: For example, postage of 8 cents is a subprogram of postage of 16 cents. But
: the optimal solution for 8 cents is just one 8 cents stamp, which is not
: part of the optimal solution for postage of 16 cents.
: I guess this problem is NPC.

avatar
r*k
8

because
But
顶牛人

【在 o*******p 的大作中提到】
: No, it is impossible to solve this problem by dynamic programming because
: this problem doesn't exhibit optimal substructure.
: For example, postage of 8 cents is a subprogram of postage of 16 cents. But
: the optimal solution for 8 cents is just one 8 cents stamp, which is not
: part of the optimal solution for postage of 16 cents.
: I guess this problem is NPC.

avatar
c*0
9
这个是典型的 LP问题吧。。。
用simplex
avatar
s*y
10
can you give more detail.
Thanks

【在 c********0 的大作中提到】
: 这个是典型的 LP问题吧。。。
: 用simplex

avatar
c*0
11
比如面值为2分,5分,8分 的邮票各
有a, b, c 张,邮资是16分
假设取2分 5分 8分 的各x,y,z 张
limitation:
0<=x<=a
0<=y<=b
0<=z<=c
2x+5y+8z >= 16
obj: min( 2x+5y+8z )
这是LP问题(他的dual是标准形式)
如果x,y,z都是整数的话是有polynomial解的 通常用simplex运行很快
可以scale到很高的维度
http://en.wikipedia.org/wiki/Linear_programming
但是我感觉通常面试不考LP的。。。
avatar
j*l
12
这是一道G的题目...
我觉得:
1) 和多重背包有一定关系,每种物品有若干件,假设物品的价值和重量成正比,这样
总价值最大就是总重量最大。不过要把不超重的情况下尽可能的重,改为超重的情况下
尽可能的轻。既然多重背包可以用动态规划,这题肯定也可以,参考楼教主的背包九讲。
2) 转为LP的问题让我耳目一新。其实我学最优化理论的时候学过单纯型法,但这题没
有想到也可以转为LP问题。不过从1)来看,应该是NPC的,用LP解是伪多项式时间吧。
不少用动态规划解的NPC题,也是伪多项式的,要弄清楚输入规模。
3) 最不济,也要想到暴力穷举法,比如你的例子,对x, y, z作三重循环。如果这个不
说出来,又想不到1)或者2), 面试官那里肯定几乎不得分了。
4) 如果想用贪心法或者硬币找零的动态规划法,这题就走弯路和死胡同了。

比如面值为2分,5分,8分 的邮票各
有a, b, c 张,邮资是16分
假设取2分 5分 8分 的各x,y,z 张
limitation:
0<=x<=a
0<=y<=b
0<=z<=c
2x+5y+8z >= 16
obj: min( 2x+5y+8z )
这是LP问题(他的dual是标准形式)
如果x,y,z都是整数的话是有polynomial解的 通常用simplex运行很快
可以scale到很高的维度
http://en.wikipedia.org/wiki/Linear_programming
但是我感觉通常面试不考LP的。。。

【在 c********0 的大作中提到】
: 比如面值为2分,5分,8分 的邮票各
: 有a, b, c 张,邮资是16分
: 假设取2分 5分 8分 的各x,y,z 张
: limitation:
: 0<=x<=a
: 0<=y<=b
: 0<=z<=c
: 2x+5y+8z >= 16
: obj: min( 2x+5y+8z )
: 这是LP问题(他的dual是标准形式)

avatar
a*e
13
可以定义一个recursive function吧每次先pick up面值v_k的邮票,剩下的邮票
只需要凑足V-v_k。对k循环做比较。但是要call很多次function,时间复杂度不低。。

讲。

【在 j**l 的大作中提到】
: 这是一道G的题目...
: 我觉得:
: 1) 和多重背包有一定关系,每种物品有若干件,假设物品的价值和重量成正比,这样
: 总价值最大就是总重量最大。不过要把不超重的情况下尽可能的重,改为超重的情况下
: 尽可能的轻。既然多重背包可以用动态规划,这题肯定也可以,参考楼教主的背包九讲。
: 2) 转为LP的问题让我耳目一新。其实我学最优化理论的时候学过单纯型法,但这题没
: 有想到也可以转为LP问题。不过从1)来看,应该是NPC的,用LP解是伪多项式时间吧。
: 不少用动态规划解的NPC题,也是伪多项式的,要弄清楚输入规模。
: 3) 最不济,也要想到暴力穷举法,比如你的例子,对x, y, z作三重循环。如果这个不
: 说出来,又想不到1)或者2), 面试官那里肯定几乎不得分了。

avatar
c*0
14
LP的问题 如果要求整数解的话不是NPC
每个邮票不是要求必须整数吗。。。
如果可以浮点数的话是NPC

讲。

【在 j**l 的大作中提到】
: 这是一道G的题目...
: 我觉得:
: 1) 和多重背包有一定关系,每种物品有若干件,假设物品的价值和重量成正比,这样
: 总价值最大就是总重量最大。不过要把不超重的情况下尽可能的重,改为超重的情况下
: 尽可能的轻。既然多重背包可以用动态规划,这题肯定也可以,参考楼教主的背包九讲。
: 2) 转为LP的问题让我耳目一新。其实我学最优化理论的时候学过单纯型法,但这题没
: 有想到也可以转为LP问题。不过从1)来看,应该是NPC的,用LP解是伪多项式时间吧。
: 不少用动态规划解的NPC题,也是伪多项式的,要弄清楚输入规模。
: 3) 最不济,也要想到暴力穷举法,比如你的例子,对x, y, z作三重循环。如果这个不
: 说出来,又想不到1)或者2), 面试官那里肯定几乎不得分了。

avatar
j*r
15
这个问题是npc的,可以规约到3-color
这里的线性规划出来的是解是在实数上的,不符合要求
如果限制在整数上,叫整数规划,是npc的。。。
avatar
c*0
16
我说反了。。。
整数解是NPC

【在 j*******r 的大作中提到】
: 这个问题是npc的,可以规约到3-color
: 这里的线性规划出来的是解是在实数上的,不符合要求
: 如果限制在整数上,叫整数规划,是npc的。。。

avatar
j*l
17
I did not realize that Brute Force method should be used first, and tried to use Greedy and the idea of Coin problem instead. I eventually got stuck. I finally told him that it should be NPC, but I did not realize that it is a variation of the classic Knapsack problem and let him know. I think he gave bad feedback to the hiring committee.
3) 最不济,也要想到暴力穷举法,比如comon2010的例子,可对x, y, z作三重循环穷举比较。如果这个都不能先说出来,然后又想不到1)或者2), 面试官那里肯定几乎不得分了。
avatar
g*s
18
assume v1,v2<...>answer = invalid;
m = V + v_n
while ( (t = 背包(m))>=V){
answer = m;
m = t-1;
}
return answer;
So, we can use 背包 function to solve this problem.

讲。

【在 j**l 的大作中提到】
: 我想这题和背包一样是NP的,不知道是否是要用动态规划来解?
: 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在
: 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。
: N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。

avatar
o*p
19
I would tell the interviewer that I can't solve this problem in polynomial
time, but I do want to know the answer if the interviewer can solve it in
polynomial time, so that I can go to Clay Institute and claim their 1
million dollar prize.

讲。

【在 j**l 的大作中提到】
: 我想这题和背包一样是NP的,不知道是否是要用动态规划来解?
: 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在
: 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。
: N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。

avatar
g*s
20
interviewer can solve it as i think.

polynomial
in

【在 o*******p 的大作中提到】
: I would tell the interviewer that I can't solve this problem in polynomial
: time, but I do want to know the answer if the interviewer can solve it in
: polynomial time, so that I can go to Clay Institute and claim their 1
: million dollar prize.
:
: 讲。

avatar
g*e
21
lol

【在 g***s 的大作中提到】
: interviewer can solve it as i think.
:
: polynomial
: in

avatar
j*y
22
请教一下楼主,这线性规划的数学模型我能理解,毕竟以前在大学里面学过。不过,用
C或者C++有专门的解法或者library吗?
还是要自己手动去求解?
avatar
r*e
23
lp_solve package

【在 j***y 的大作中提到】
: 请教一下楼主,这线性规划的数学模型我能理解,毕竟以前在大学里面学过。不过,用
: C或者C++有专门的解法或者library吗?
: 还是要自己手动去求解?

avatar
j*y
24
顺便再请教一下,NPC是什么意思啊?
谢谢
avatar
y*m
25
ms题意只要求最接近V没要求邮票张数也最少吧? how about this?
邮票数组a,邮票张数数组c
看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模,一旦找到模为0退出循环
如果要求最少张数就把金额排序再递归
V = 358;
array a[]={0,2,3,5....n}; //邮票金额
array c[]={0,55,13,5,...n}; //邮票张数
array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数
array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数
calc(V, 1); //算出 pick 数组
int minMod=1000000000000;
function calc(V,j){
int i = V/a[j] > c[j] ? c[j]:V/a[j];
for(;i>-1;i--){
if(i>c[j])
continued;//大于预定的邮票张数继续-1

int imod = V - i*a[j];
current[j] = i;//记录当前邮票张数
//找到最接近V
if( imod == 0 ){
setPickArray(imod);
break;
}
//当前邮票币值满足接近V的先记录下来
if( imod < a[j] && ( i < c[j] ) ){
imod = a[j] - imod;
current[j] = i+1;//记录当前邮票张数
setPickArray(imod);
continued;
}
//如果还有币值,继续递归到下一币值
if( j < a.size() )
calc( imod , j+1 );
//如果到了最后一个币值,记录最接近V的组合合
else
setPickArray(imod);
}
}
function setPickArray(int imod){
if( minMod > imod ){
minMod = imod;
for(int i=0; i < current.size(); i++){
pick[i] = current[i];
current[i] = 0;
}
}
}

讲。

【在 j**l 的大作中提到】
: 我想这题和背包一样是NP的,不知道是否是要用动态规划来解?
: 有N种邮票,面值分别为v_1, v_2, ..., v_N, 张数分别为c_1, c_2, ..., c_N。现在
: 要邮寄的包裹需要的邮资是V, 如何选取邮票,使得总面值>=V, 且尽可能的小。
: N, v_1, v_2, ..., v_N, c_1, c_2, ..., c_N都是给定的正整数。

avatar
j*y
26
楼上的兄弟,能不能给点注释啊?看不懂啊,尤其是对我这样算法不熟的人。
你这个算法有英文名称吗?
current数组是干啥用的啊?
calc()的功用是什么?两个形参是干啥的呀?
avatar
y*m
27
注了,其实是从找硬币组合的变种,就是递归求模...

【在 j***y 的大作中提到】
: 楼上的兄弟,能不能给点注释啊?看不懂啊,尤其是对我这样算法不熟的人。
: 你这个算法有英文名称吗?
: current数组是干啥用的啊?
: calc()的功用是什么?两个形参是干啥的呀?

avatar
g*s
28
这个算法的复杂度 O(Nb * V * v_N)
Nb表示硬币的总个数。
m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N)
细节有些可以提高。
估计这个面试官想要的结果。

【在 g***s 的大作中提到】
: assume v1,v2<...>: answer = invalid;
: m = V + v_n
: while ( (t = 背包(m))>=V){
: answer = m;
: m = t-1;
: }
: return answer;
: So, we can use 背包 function to solve this problem.
:

avatar
j*y
29

循环
谢谢添加注释,虽然我还是没怎么看懂。:-(
顺便再问一下,code里面的for循环似乎少一个结尾的花括号。

【在 y***m 的大作中提到】
: ms题意只要求最接近V没要求邮票张数也最少吧? how about this?
: 邮票数组a,邮票张数数组c
: 看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模,一旦找到模为0退出循环
: 如果要求最少张数就把金额排序再递归
: V = 358;
: array a[]={0,2,3,5....n}; //邮票金额
: array c[]={0,55,13,5,...n}; //邮票张数
: array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数
: array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数
: calc(V, 1); //算出 pick 数组

avatar
y*m
30
呵呵,补上了,时间复杂度?依赖于V,sumA,c..

【在 j***y 的大作中提到】
:
: 循环
: 谢谢添加注释,虽然我还是没怎么看懂。:-(
: 顺便再问一下,code里面的for循环似乎少一个结尾的花括号。

avatar
m*g
31
弱问这题用多重背包的思路代码怎么写?
谢谢!

这个算法的复杂度 O(Nb * V * v_N)
Nb表示硬币的总个数。
m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N)
细节有些可以提高。
估计这个面试官想要的结果。

【在 g***s 的大作中提到】
: 这个算法的复杂度 O(Nb * V * v_N)
: Nb表示硬币的总个数。
: m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N)
: 细节有些可以提高。
: 估计这个面试官想要的结果。

avatar
g*s
32
Since the DP stores all the values, we don't need to handle (log v_N) times.
So, it is same time complexity of Knapsack problem.
new_V < 2*V
Knapsack can be handle in O(N*V), so this question can be handled in O(N*2*V
) = O(N*V). N is the type of coins.
the O(N*V) codes for knapsack are hard to read. following is sample codes,
time = O(V * sigma log s_i) .
public static int getMinStampNum(Coin[] coins, int V) {
ArrayList p = new ArrayList();
for (Coin coin : coins) {
int value = coin.faceValue;
int num = Math.min(coin.num, V / value + 1);
int g = 1;
while (num > 0) {
int t = Math.min(g, num);
num -= t;
p.add(value * t);
g <<= 1;
}
}
Collections.sort(p);
int newV = getNewV(p, V);
if (p.size() == 1 && p.get(0) >= V) return p.get(0);
int[][] opt = buildBy01Knapsack(p, V + p.get(p.size() - 1) - 1);
for (int i = V; i <= newV; i++) {
if (opt[p.size() - 1][i] >= V) return i;
}
return -1;
}
//simple version, easy to understand, but time complexity is large to
handle this case: (1,1), (2,2), (100000000,10) V=30
private static int getNewV_SimpleVersion(ArrayList p, int V) {
return V + p.get(p.size() - 1) - 1;
}
private static int getNewV(ArrayList p, int V) {
int sum = 0;
for (int i = 0; i < p.size(); i++) {
int value = p.get(i);
if (value >= V) {
if (sum < V) {
//sum of the previous items is less than V, so we just
pick up the current value;
p.clear();
p.add(value);
return value;
}
int pos = sum < value ? i : i + 1;
while (p.size() > pos) p.remove(pos);
return Math.min(sum, value);
}
if (sum < V) sum += p.get(i);
}
return sum;
}
private static int[][] buildBy01Knapsack(ArrayList p, int V) {
int[][] result = new int[p.size()][V + 1];
for (int i = 0; i < result.length; i++)
for (int v = 1; v <= V; v++) {
int value1 = (i == 0) ? 0 : result[i - 1][v];
int value2 = (v >= p.get(i)) ? p.get(i) + ((i == 0) ? 0 :
result[i - 1][v - p.get(i)]) : 0;
result[i][v] = Math.max(value1, value2);
}
return result;
}
static class Coin {
int faceValue;
int num;
Coin(int f, int n) {
faceValue = f;
num = n;
}
}

【在 g***s 的大作中提到】
: 这个算法的复杂度 O(Nb * V * v_N)
: Nb表示硬币的总个数。
: m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N)
: 细节有些可以提高。
: 估计这个面试官想要的结果。

avatar
g*s
33
posted codes just now.

【在 m***g 的大作中提到】
: 弱问这题用多重背包的思路代码怎么写?
: 谢谢!
:
: 这个算法的复杂度 O(Nb * V * v_N)
: Nb表示硬币的总个数。
: m的取发可以用二分,那么可以提高到 O(Nb * V * log v_N)
: 细节有些可以提高。
: 估计这个面试官想要的结果。

avatar
m*g
34
太牛了,可是太复杂没大看懂,有形象的图或简单文字描述算法思路和步骤么?
谢谢!

times.
*V

【在 g***s 的大作中提到】
: Since the DP stores all the values, we don't need to handle (log v_N) times.
: So, it is same time complexity of Knapsack problem.
: new_V < 2*V
: Knapsack can be handle in O(N*V), so this question can be handled in O(N*2*V
: ) = O(N*V). N is the type of coins.
: the O(N*V) codes for knapsack are hard to read. following is sample codes,
: time = O(V * sigma log s_i) .
: public static int getMinStampNum(Coin[] coins, int V) {
: ArrayList p = new ArrayList();
: for (Coin coin : coins) {

avatar
g*e
35
先顶再看

times.
*V

【在 g***s 的大作中提到】
: Since the DP stores all the values, we don't need to handle (log v_N) times.
: So, it is same time complexity of Knapsack problem.
: new_V < 2*V
: Knapsack can be handle in O(N*V), so this question can be handled in O(N*2*V
: ) = O(N*V). N is the type of coins.
: the O(N*V) codes for knapsack are hard to read. following is sample codes,
: time = O(V * sigma log s_i) .
: public static int getMinStampNum(Coin[] coins, int V) {
: ArrayList p = new ArrayList();
: for (Coin coin : coins) {

avatar
m*g
36
请问这是穷举么?递归效率是否比较低?

余邮票额
【在 y***m 的大作中提到】
: ms题意只要求最接近V没要求邮票张数也最少吧? how about this?
: 邮票数组a,邮票张数数组c
: 看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模,一旦找到模为0退出循环
: 如果要求最少张数就把金额排序再递归
: V = 358;
: array a[]={0,2,3,5....n}; //邮票金额
: array c[]={0,55,13,5,...n}; //邮票张数
: array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数
: array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数
: calc(V, 1); //算出 pick 数组

avatar
t*d
37
let S = v_1*c_1 + v_2*c_2 + ... + v_n*c_n;
if S < V no solution
else let R = S - V
solve the knapsack problem with capacity of R
avatar
m*g
38
没看懂,好像只是重复了一下题目要求么?

【在 t******d 的大作中提到】
: let S = v_1*c_1 + v_2*c_2 + ... + v_n*c_n;
: if S < V no solution
: else let R = S - V
: solve the knapsack problem with capacity of R

avatar
g*s
39
这个有问题。反例
(9,2) V=10
S=18
S-V=8
背包得0

【在 m***g 的大作中提到】
: 没看懂,好像只是重复了一下题目要求么?
avatar
t*d
40

I probably didn't make it clear.
After you solve the knapsack of S-V, that's the stamps you can save.
In your case you save 0 stamps, i.e. you need to use all the stamps

【在 g***s 的大作中提到】
: 这个有问题。反例
: (9,2) V=10
: S=18
: S-V=8
: 背包得0

avatar
g*s
41
another sample (5,4) 11
S=20
S-V=9
knapsack(9) = 0;
if you pickup all, the sum is 20. but the correct answer is 15.

【在 t******d 的大作中提到】
:
: I probably didn't make it clear.
: After you solve the knapsack of S-V, that's the stamps you can save.
: In your case you save 0 stamps, i.e. you need to use all the stamps

avatar
t*d
42

As I said, you can save one stamp with 5 face value, which means you need
to use another three stamps.

【在 g***s 的大作中提到】
: another sample (5,4) 11
: S=20
: S-V=9
: knapsack(9) = 0;
: if you pickup all, the sum is 20. but the correct answer is 15.

avatar
g*s
43
yes. your method is right.
but S could be >> V. some samples:
(1,10000000) 5
(1,1) (2,1) (100000000,1) 5

【在 t******d 的大作中提到】
:
: As I said, you can save one stamp with 5 face value, which means you need
: to use another three stamps.

avatar
m*g
44
弱问,背包问题是 2个条件(价值,重量)其中一个是固定的,这题是2个条件(价值
,张数) 都是没限制的,怎么关联到一块?

As I said, you can save one stamp with 5 face value, which means you need
to use another three stamps.

【在 t******d 的大作中提到】
:
: As I said, you can save one stamp with 5 face value, which means you need
: to use another three stamps.

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。