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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 据这个题目只用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 据这个题目只用25即可
|
s*i 发帖数: 5025 | 9 版上没见过这道题
【在 f*********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有什么tricky的地方吗? 为啥说是newest coding problem。求指导 : : you : complexity?
|