s*i
发帖数: 5025 | 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***k
发帖数: 161 | 2 naive solution：dfs找出所有组合再扫一遍找最大的。。。
请问这是哪家的题目？ |
p**p
发帖数: 742 | 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***n
发帖数: 58 | |
s*i
发帖数: 5025 | 5 显然不是
[发表自未名空间手机版 - m.mitbbs.com]
【在 w***n 的大作中提到】
: 据这个题目只用25即可
|
f*********0
发帖数: 17 | 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*********0
发帖数: 17 | 7 有什么tricky的地方吗？ 为啥说是newest coding 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?
|
b******g
发帖数: 3616 | 8 显然不能只用25吧。。。反过来如果是用cash buy point那是只用25就行了。。。
【在 w***n 的大作中提到】
: 据这个题目只用25即可
|
s*i
发帖数: 5025 | 9 版上没见过这道题
【在 f*********0 的大作中提到】
: 有什么tricky的地方吗？ 为啥说是newest coding problem。求指导
:
: you
: complexity?
|
