捡金子 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是按照最小的来写的。后来才发现是要求最大。
相关阅读
急求一 Offer Letter，请网上各位兄弟姐妹帮忙 (转载)有人能介绍一下Google 分组的情况吗？Onsite完 hr 说“holding pattern”是不是就是备胎的意思什么是RPS?A家电面收到epic的offer, 求教有关的问题求LinkedIn内推想学spark，有书能推荐吗？波士顿contract position:Excel / VBA Consultant( 0-2 years experience)G家onsite加面问一个题，求相同元素最多的两个数组三个volunteer工作刚发的贴子找不着了, 神马情况?hiring manager说面试可以用任何language，但是有个工程师非要用javatumblr这家 技术如何？公司如何？版里是不是大部分是软件的?intel的export license到底需要多久？H1B transfer approved 还没收到邮寄的approval notice可以工作吗工作8个月流水帐就new grad而言, FLG怎么排序??