求解比硬币找零稍难的一题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求解比硬币找零稍难的一题

求解比硬币找零稍难的一题# JobHunting - 待字闺中

j*l2011-03-23 07:03

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都是给定的正整数。

s*y2011-03-23 07:03

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都是给定的正整数。

j*l2011-03-23 07:03

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 尽可能的小?

g*s2011-03-23 07:03

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分。

r*k2011-03-23 07:03

5 楼

子最有解不好转换成当前最优解啊。。。

o*p2011-03-23 07:03

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 的大作中提到】

s*y2011-03-23 07:03

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.

r*k2011-03-23 07:03

8 楼

because
But
顶牛人

【在 o*******p 的大作中提到】

c*02011-03-23 07:03

9 楼

这个是典型的 LP问题吧。。。
用simplex

s*y2011-03-23 07:03

10 楼

can you give more detail.
Thanks

【在 c********0 的大作中提到】

: 这个是典型的 LP问题吧。。。
: 用simplex

c*02011-03-23 07:03

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的。。。

j*l2011-03-23 07:03

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是标准形式）

a*e2011-03-23 07:03

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), 面试官那里肯定几乎不得分了。

c*02011-03-23 07:03

14 楼

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

讲。

【在 j**l 的大作中提到】

j*r2011-03-23 07:03

15 楼

这个问题是npc的，可以规约到3-color
这里的线性规划出来的是解是在实数上的，不符合要求
如果限制在整数上，叫整数规划，是npc的。。。

c*02011-03-23 07:03

16 楼

我说反了。。。
整数解是NPC

【在 j*******r 的大作中提到】

: 这个问题是npc的，可以规约到3-color
: 这里的线性规划出来的是解是在实数上的，不符合要求
: 如果限制在整数上，叫整数规划，是npc的。。。

j*l2011-03-23 07:03

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), 面试官那里肯定几乎不得分了。

g*s2011-03-23 07:03

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 的大作中提到】

o*p2011-03-23 07:03

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 的大作中提到】

g*s2011-03-23 07:03

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.
:
: 讲。

g*e2011-03-23 07:03

21 楼

lol

【在 g***s 的大作中提到】

: interviewer can solve it as i think.
:
: polynomial
: in

j*y2011-03-23 07:03

22 楼

请教一下楼主，这线性规划的数学模型我能理解，毕竟以前在大学里面学过。不过，用
C或者C++有专门的解法或者library吗？
还是要自己手动去求解？

r*e2011-03-23 07:03

23 楼

lp_solve package

【在 j***y 的大作中提到】

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

j*y2011-03-23 07:03

24 楼

顺便再请教一下，NPC是什么意思啊？
谢谢

y*m2011-03-23 07:03

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 的大作中提到】

j*y2011-03-23 07:03

26 楼

楼上的兄弟，能不能给点注释啊？看不懂啊，尤其是对我这样算法不熟的人。
你这个算法有英文名称吗？
current数组是干啥用的啊？
calc()的功用是什么？两个形参是干啥的呀？

y*m2011-03-23 07:03

27 楼

注了，其实是从找硬币组合的变种,就是递归求模...

【在 j***y 的大作中提到】

: 楼上的兄弟，能不能给点注释啊？看不懂啊，尤其是对我这样算法不熟的人。
: 你这个算法有英文名称吗？
: current数组是干啥用的啊？
: calc()的功用是什么？两个形参是干啥的呀？

g*s2011-03-23 07:03

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.
:

j*y2011-03-23 07:03

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 数组

y*m2011-03-23 07:03

30 楼

呵呵，补上了，时间复杂度？依赖于V,sumA,c..

【在 j***y 的大作中提到】

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

m*g2011-03-23 07:03

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)
: 细节有些可以提高。
: 估计这个面试官想要的结果。

g*s2011-03-23 07:03

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 的大作中提到】

g*s2011-03-23 07:03

33 楼

posted codes just now.

【在 m***g 的大作中提到】

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

m*g2011-03-23 07:03

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) {

g*e2011-03-23 07:03

35 楼

先顶再看

times.
*V

【在 g***s 的大作中提到】

m*g2011-03-23 07:03

36 楼

请问这是穷举么？递归效率是否比较低?

余邮票额
【在 y***m 的大作中提到】

t*d2011-03-23 07:03

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

m*g2011-03-23 07:03

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

g*s2011-03-23 07:03

39 楼

这个有问题。反例
（9，2） V=10
S=18
S-V=8
背包得0

【在 m***g 的大作中提到】

: 没看懂，好像只是重复了一下题目要求么?

t*d2011-03-23 07:03

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

g*s2011-03-23 07:03

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

t*d2011-03-23 07:03

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.

g*s2011-03-23 07:03

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.

m*g2011-03-23 07:03

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.