t*******e
发帖数: 274 | 1 最近遇到的一道题，用java实现，结果要是在单个class内，还要有test case验证，有
人知道么？
题目： Given a set of retrofitting options (String name, double cost, double
benefit), and a budget, produce the highest benefit subset whose total cost
fits within the budget. Repeat this exercise, given a set of mutual
exclusivity constraints (i.e. measure X and measure Y cannot be used
together) | i*****r
发帖数: 265 | 2 Isn't it NP-complete? Knapsack? | h**k
发帖数: 3368 | 3 polynomial时间不可能找到最优解，这个是NP-hard问题。
exponential solution: check every possible subset of strings.
linear approximating solution: Greedy algorithm. calculate rate of benefit
to cost, then always choose maximal rate string first.
double
cost
【在 t*******e 的大作中提到】
: 最近遇到的一道题，用java实现，结果要是在单个class内，还要有test case验证，有
: 人知道么？
: 题目： Given a set of retrofitting options (String name, double cost, double
: benefit), and a budget, produce the highest benefit subset whose total cost
: fits within the budget. Repeat this exercise, given a set of mutual
: exclusivity constraints (i.e. measure X and measure Y cannot be used
: together)
|
|
