捡金子 An interview question# JobHunting - 待字闺中
b*y
1 楼
Give you a bag in a room with different sizes of golds. Pick up max amount
into the bag.
int PickUpGold(int[] golds, int capacity);
into the bag.
int PickUpGold(int[] golds, int capacity);
N*p
2 楼
好NP的问题。。。
【在 b*********y 的大作中提到】
: Give you a bag in a room with different sizes of golds. Pick up max amount
: into the bag.
: int PickUpGold(int[] golds, int capacity);
【在 b*********y 的大作中提到】
: Give you a bag in a room with different sizes of golds. Pick up max amount
: into the bag.
: int PickUpGold(int[] golds, int capacity);
b*y
3 楼
没有好的思路
y*g
4 楼
经典背包
w*o
5 楼
每个金子块的面值不同？金子的物理尺寸和价值有什么关系吗？
这个bag的形状是什么？金子的形状？是不是要最优的去摆放呀？！
【在 b*********y 的大作中提到】
: Give you a bag in a room with different sizes of golds. Pick up max amount
: into the bag.
: int PickUpGold(int[] golds, int capacity);
这个bag的形状是什么？金子的形状？是不是要最优的去摆放呀？！
【在 b*********y 的大作中提到】
: Give you a bag in a room with different sizes of golds. Pick up max amount
: into the bag.
: int PickUpGold(int[] golds, int capacity);
p*2
6 楼
int PickUpGold(int[] golds, int capacity)
{
int[] dp=new int[capacity+1];
dp[0]=0;
for(int i=1;i<=capacity;i++)
{
int max=0;
for(int j=0;j
max=Math.max(max,1+dp[i-golds[j]]);
dp[i]=max;
}
return dp[capacity];
}
{
int[] dp=new int[capacity+1];
dp[0]=0;
for(int i=1;i<=capacity;i++)
{
int max=0;
for(int j=0;j
max=Math.max(max,1+dp[i-golds[j]]);
dp[i]=max;
}
return dp[capacity];
}
s*r
7 楼
如果不止一个包，要怎么算呢？
【在 y*******g 的大作中提到】
: 经典背包
【在 y*******g 的大作中提到】
: 经典背包
d*e
8 楼
变成一个大包
【在 s**********r 的大作中提到】
: 如果不止一个包，要怎么算呢？
【在 s**********r 的大作中提到】
: 如果不止一个包，要怎么算呢？
w*o
9 楼
什么是"max amount "? 是指能放进去的金块的个数吗？
觉得这个题很荒谬的，就挑size最小的放就好了。
这个题到底是在说什么？
谢谢！
【在 b*********y 的大作中提到】
: Give you a bag in a room with different sizes of golds. Pick up max amount
: into the bag.
: int PickUpGold(int[] golds, int capacity);
觉得这个题很荒谬的，就挑size最小的放就好了。
这个题到底是在说什么？
谢谢！
【在 b*********y 的大作中提到】
: Give you a bag in a room with different sizes of golds. Pick up max amount
: into the bag.
: int PickUpGold(int[] golds, int capacity);
p*2
10 楼
是不是最小个数呀？我刚才写code是按照最小的来写的。后来才发现是要求最大。
【在 w****o 的大作中提到】
: 什么是"max amount "? 是指能放进去的金块的个数吗？
: 觉得这个题很荒谬的，就挑size最小的放就好了。
: 这个题到底是在说什么？
: 谢谢！
y*g
11 楼
面试遇到这个级别的题目直接放弃
【在 s**********r 的大作中提到】
: 如果不止一个包，要怎么算呢？
【在 s**********r 的大作中提到】
: 如果不止一个包，要怎么算呢？
s*r
12 楼
真的假的啊？
不是吧。。。
【在 d**e 的大作中提到】
: 变成一个大包
不是吧。。。
【在 d**e 的大作中提到】
: 变成一个大包
d*e
13 楼
sorry....我以为我们还在俱乐部开开玩笑。。。。
【在 s**********r 的大作中提到】
: 真的假的啊？
: 不是吧。。。
【在 s**********r 的大作中提到】
: 真的假的啊？
: 不是吧。。。
s*r
14 楼
那咱们赶紧转回我们那个自闭俱乐部去～
【在 d**e 的大作中提到】
: sorry....我以为我们还在俱乐部开开玩笑。。。。
【在 d**e 的大作中提到】
: sorry....我以为我们还在俱乐部开开玩笑。。。。
b*u
15 楼
public static int PickUpGold(List golds, int capacity)
{
int max = 0;
if (golds.Count == 1)
{
if (golds[0] <= capacity)
{
max = golds[0];
}
}
else if (golds.Count > 1 )
{
for (int i=0; i< golds.Count; i++ )
{
List gs = golds.ToList();
int total = golds[i];
if (capacity - golds[i] > 0)
{
gs.RemoveAt(i);
total += PickUpGold(gs, capacity - golds[i]);
}
if (total > max && total <= capacity )
{
max = total;
if (max == capacity)
{
break;
}
}
}
}
return max;
}
{
int max = 0;
if (golds.Count == 1)
{
if (golds[0] <= capacity)
{
max = golds[0];
}
}
else if (golds.Count > 1 )
{
for (int i=0; i< golds.Count; i++ )
{
List
int total = golds[i];
if (capacity - golds[i] > 0)
{
gs.RemoveAt(i);
total += PickUpGold(gs, capacity - golds[i]);
}
if (total > max && total <= capacity )
{
max = total;
if (max == capacity)
{
break;
}
}
}
}
return max;
}
S*h
16 楼
v587
【在 p*****2 的大作中提到】
:
: 是不是最小个数呀？我刚才写code是按照最小的来写的。后来才发现是要求最大。
【在 p*****2 的大作中提到】
:
: 是不是最小个数呀？我刚才写code是按照最小的来写的。后来才发现是要求最大。
相关阅读
借人气，速问一个问题。Amazon is hiring senior UI/Front end Developers-Seattle/WA控诉一下recruiter 加 咨询关于OPT -> H1B Cap-Gap Extension 的一个疑问投了简历， 然后收到公司 的电话留言，什么时候回比较好onsite面试完后要写感谢信么？面试经验分享What is the status of my OPT?急，专门发帖问一下manufacturing到底是什么概念啊【绝无仅有的超差人品】H1B 申请了 将近11个月都没批下来！！！！！non recursive binary tree traversal in O(n) time and O(1) space面试时不会的题目可以pass吗？申请OPT的一个问题。寻找下一个回文数论坛新人，电面求祝福心情真是非常 blue ， 已经1年多了，还有希望找到工作吗聊聊最近面试的几个candidates办11年的H1b应该怎么准备资料?新年第一个onsite，向万能的JobHunting求祝福，也祝福大家