父母ｂ２签证延期特殊问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Reunion - 探亲与陪读

父母ｂ２签证延期特殊问题

父母ｂ２签证延期特殊问题# Reunion - 探亲与陪读

E*n2013-11-28 08:11

1 楼

给定一个整数数组，从大到小已经排好序，比如
30， 23， 10， 5， 2， 1
再给定一个整数，比如80，用给定数组中的元素来凑成80，比如 80 = 30 + 30 + 10
+ 10
使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
我没有好的idea，
恳请高手指教！
刚才忘了说，1是永远存在数列里面的

f*i2013-11-28 08:11

2 楼

我父母上半年申请ｂ２的时候我还是h1b 在等绿卡，现在拿到绿卡几个月了，现在填表
时有一项问
Are you filing this benefit request for status based on a Principal Alien's
nonimmigrant status? 我改选ｙｅｓ　ｏｒ　ｎｏ　呢？
多谢！

s*t2013-11-28 08:11

3 楼

google 背包问题

10

【在 E***n 的大作中提到】

: 给定一个整数数组，从大到小已经排好序，比如
: 30， 23， 10， 5， 2， 1
: 再给定一个整数，比如80，用给定数组中的元素来凑成80，比如 80 = 30 + 30 + 10
: + 10
: 使得使用的元素个数最少（这个题目很像”找钱“，用有限的纸币的面值才凑数）。
: 我没有好的idea，
: 恳请高手指教！
: 刚才忘了说，1是永远存在数列里面的

p*w2013-11-28 08:11

4 楼

从大往小凑。
凑不成功之后，就回退一级

10

【在 E***n 的大作中提到】

B*t2013-11-28 08:11

5 楼

NPC, 没什么通用的好方法。
如果数的个数小于25，DFS效率好一些。
否则的话用 psudo-polynomial的背包问题的标准解法。

10

【在 E***n 的大作中提到】

E*n2013-11-28 08:11

6 楼

谢谢
但是这样不一定能找到最少的.如果我给定数组
10， 7， 1
要求凑14，那么从大往小凑需要14 = 10 + 1 + 1 + 1 + 1,实际上14 = 7 + 7，只要2个

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

: 从大往小凑。
: 凑不成功之后，就回退一级
:
: 10

s*t2013-11-28 08:11

7 楼

可以重复使用也没关系
总之思路就是贪心地试验

2个

【在 E***n 的大作中提到】

: 谢谢
: 但是这样不一定能找到最少的.如果我给定数组
: 10， 7， 1
: 要求凑14，那么从大往小凑需要14 = 10 + 1 + 1 + 1 + 1,实际上14 = 7 + 7，只要2个

b*g2013-11-28 08:11

8 楼

hehe, very nice. It is a NPC problem like subset sum problem.

【在 B*****t 的大作中提到】

: NPC, 没什么通用的好方法。
: 如果数的个数小于25，DFS效率好一些。
: 否则的话用 psudo-polynomial的背包问题的标准解法。
:
: 10

r*o2013-11-28 08:11

9 楼

能不能贴一下代码或pseudo code?
多谢。

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

: 从大往小凑。
: 凑不成功之后，就回退一级
:
: 10

y*i2013-11-28 08:11

10 楼

回溯法可以么

10

【在 E***n 的大作中提到】

E*n2013-11-28 08:11

11 楼

不能这么做，我最后用了dynamic programming.
Grady algorithm可能无法得到正确的结果，除非穷举，但是这样太慢了

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

: 可以重复使用也没关系
: 总之思路就是贪心地试验
:
: 2个

r*o2013-11-28 08:11

12 楼

你说的Greedy algorithm是用DFS搜索吗？

【在 E***n 的大作中提到】

: 不能这么做，我最后用了dynamic programming.
: Grady algorithm可能无法得到正确的结果，除非穷举，但是这样太慢了

E*n2013-11-28 08:11

13 楼

dynamic programming,
和费波纳契数列比较类似
Backtracking可能需要返回不止一次，所以太麻烦了

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

: 回溯法可以么
:
: 10

n*r2013-11-28 08:11

14 楼

Nice exercise for practising Knapsack problem
Let all items having weight 1, i.e. w_i=1, p_i being item i's value, A(Y)
being the min weight that can be achieved with total money Y (achieveable
becasue 1 is always there)
Then
A(0) = 0
A(Y)=min{1+A(Y-p_i)|p_i≤Y}
Calculate A(1),A(2),..., till you get A(80)
What kind of position is this interview for?

10

【在 E***n 的大作中提到】