Newest coding problem - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Newest coding problem

Newest coding problem# JobHunting - 待字闺中

s*i2014-11-19 08:11

1 楼

You were given 858 points to buy 'cash'. Here is the available lots that you
can only choose from:
(cash value : points required)
$25 28p
$50 53p
$75 78p
$100 103p
$250 255p
$500 510p
Find the best combination so that you get max $. What is the time complexity?

h*k2014-11-19 08:11

2 楼

naive solution：dfs找出所有组合再扫一遍找最大的。。。
请问这是哪家的题目？

p*p2014-11-19 08:11

3 楼

Isn't it just a regular backsack problem?

you
complexity?

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

: You were given 858 points to buy 'cash'. Here is the available lots that you
: can only choose from:
: (cash value : points required)
: $25 28p
: $50 53p
: $75 78p
: $100 103p
: $250 255p
: $500 510p
: Find the best combination so that you get max $. What is the time complexity?

w*n2014-11-19 08:11

4 楼

据这个题目只用25即可

s*i2014-11-19 08:11

5 楼

显然不是

[发表自未名空间手机版 - m.mitbbs.com]

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

: 据这个题目只用25即可

f*02014-11-19 08:11

6 楼

写了个dp的方法：
dp[i] 表示用i个point最多能买到的cash。复杂度是O(拥有的point数 * 物品数)。
这个和背包问题完全一样啊。
Reply wsnmn, 注意这里使用point买cash，不是用cash买point。
int knapsack(vector &cash, vector &point) {
int dp[859] = {0};
int n = cash.size();
for (int i = 1; i <= 858; ++i) {
for (int j = 0; j < n; ++j) {
if (i-point[j] >=0) {
dp[i] = max(dp[i], dp[i-point[j]]+cash[j]);
}
}
}
return dp[858];
}

f*02014-11-19 08:11

7 楼

有什么tricky的地方吗？为啥说是newest coding problem。求指导

you
complexity?

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