深夜情色園 2017-3-19 04:26:28 即場問你一條問題！

有個賊走左入珠寶鋪爆格，佢最多可以拎n kg既野走人，呢到有一堆珠寶

Name Price Weight
A 163 12
B 221 31
C 124 5
D 582 20
E 631 30
F 198 7
G 317 20
...

求個賊最多可以拎到幾多錢既珠寶走

:^(

深夜情色園 2017-3-19 04:28:06 請用code implement
呢條係一條經典既algorithm題目，knapsack problem
最好唔好google搵solution黎答

:^(

試下靠自己

德布羅意 2017-3-19 06:09:24 我想問stm32 HAL driver 既uart Dma buffer 點寫

:^(

Receive Interrupt唔到

:^(

三七二十一 2017-3-19 06:41:33

我想問stm32 HAL driver 既uart Dma buffer 點寫

:^(

Receive Interrupt唔到

:^(

你有冇download stm32CubeMX，或者例如你粒MCU係stm32f3, 就直接download stm32CubeF3, 再睇佢裡面for 唔到development board 嘅sample code, 一般都有UART with DMA 嘅example

傳奇 2017-3-19 07:04:37 除左recurrsion真係唔識，乖乖地Google

:^(

張無忌 2017-3-19 07:43:53 when n = 0, max weight = 0
when n = 1, max weight = 0
when n = 2, max weight = 0
when n = 3, max weight = 0
when n = 4, max weight = 0
when n = 5, max weight = 124
when n = 6, max weight = 124
when n = 7, max weight = 198
when n = 8, max weight = 198
when n = 9, max weight = 198
when n = 10, max weight = 198
when n = 11, max weight = 198
when n = 12, max weight = 322
when n = 13, max weight = 322
when n = 14, max weight = 322
when n = 15, max weight = 322
when n = 16, max weight = 322
when n = 17, max weight = 322
when n = 18, max weight = 322
when n = 19, max weight = 361
when n = 20, max weight = 582
when n = 21, max weight = 582
when n = 22, max weight = 582
when n = 23, max weight = 582
when n = 24, max weight = 582
when n = 25, max weight = 706
when n = 26, max weight = 706
when n = 27, max weight = 780
when n = 28, max weight = 780
when n = 29, max weight = 780
when n = 30, max weight = 780
when n = 31, max weight = 780
when n = 32, max weight = 904
when n = 33, max weight = 904
when n = 34, max weight = 904
when n = 35, max weight = 904
when n = 36, max weight = 904
when n = 37, max weight = 904
when n = 38, max weight = 904
when n = 39, max weight = 943
when n = 40, max weight = 943
when n = 41, max weight = 943
when n = 42, max weight = 953
when n = 43, max weight = 953
when n = 44, max weight = 1067
when n = 45, max weight = 1067
when n = 46, max weight = 1067
when n = 47, max weight = 1097
when n = 48, max weight = 1097
when n = 49, max weight = 1097
when n = 50, max weight = 1213
when n = 51, max weight = 1213
when n = 52, max weight = 1221
when n = 53, max weight = 1221
when n = 54, max weight = 1221
when n = 55, max weight = 1337
when n = 56, max weight = 1337
when n = 57, max weight = 1411
when n = 58, max weight = 1411
when n = 59, max weight = 1411
when n = 60, max weight = 1411
when n = 61, max weight = 1411
when n = 62, max weight = 1535
when n = 63, max weight = 1535
when n = 64, max weight = 1535
when n = 65, max weight = 1535
when n = 66, max weight = 1535
when n = 67, max weight = 1535
when n = 68, max weight = 1535
when n = 69, max weight = 1574
when n = 70, max weight = 1574
when n = 71, max weight = 1574
when n = 72, max weight = 1574
when n = 73, max weight = 1574
when n = 74, max weight = 1698
when n = 75, max weight = 1698
when n = 76, max weight = 1698
when n = 77, max weight = 1728
when n = 78, max weight = 1728
when n = 79, max weight = 1728
when n = 80, max weight = 1728
when n = 81, max weight = 1728
when n = 82, max weight = 1852
when n = 83, max weight = 1852
when n = 84, max weight = 1852
when n = 85, max weight = 1852
when n = 86, max weight = 1852
when n = 87, max weight = 1852
when n = 88, max weight = 1852
when n = 89, max weight = 1891
when n = 90, max weight = 1891
when n = 91, max weight = 1891
when n = 92, max weight = 1891
when n = 93, max weight = 1891
when n = 94, max weight = 2015
when n = 95, max weight = 2015
when n = 96, max weight = 2015
when n = 97, max weight = 2015
when n = 98, max weight = 2015
when n = 99, max weight = 2015
when n = 100, max weight = 2015
...

叛逆的斯奧 2017-3-19 08:21:12 max price 定weight

:^(

德布羅意 2017-3-19 12:13:17

我想問stm32 HAL driver 既uart Dma buffer 點寫

:^(

Receive Interrupt唔到

:^(

你有冇download stm32CubeMX，或者例如你粒MCU係stm32f3, 就直接download stm32CubeF3, 再睇佢裡面for 唔到development board 嘅sample code, 一般都有UART with DMA 嘅example

一直都用cube，但example太少

:^(

Pythonic 2017-3-19 12:49:59 munkres algorithm ?

張無忌 2017-3-19 14:09:13

max price 定weight

:^(

係 when n = XX, max price = YY 先啱

屁股露罅 2017-3-19 14:25:23 初心者 係學校讀緊java留名學野

:^(

風雪不等人@FLYss 2017-3-19 21:28:47 寫完呢個喇

:^(

有冇下一題？

比古清十郎 2017-3-19 21:33:06 此回覆已被刪除

膠不可登 2017-3-19 21:49:37

munkres algorithm ?

上網睇過好似係one to one關係, 好似唔岩用

:^(

狐狸叔叔 2017-3-20 12:54:34 經典DP

:^(

沢村栄純 2017-3-20 13:20:14 答到一半發覺唔work
偷偷地去google
np complete

:^(

:^(

有錢窮撚 2017-3-20 13:27:47 做緊

:^(

，等陣post上黎睇下岩唔岩

:^(

有錢窮撚 2017-3-20 13:34:47 package lihkg_problem_package;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class Lihkg_Problem {

public static void main(String[] args) {

List<Jewelry> _list = new ArrayList<>();
_list.add(new Jewelry(163, 12));
_list.add(new Jewelry(221, 31));
_list.add(new Jewelry(124, 5));
_list.add(new Jewelry(582, 20));
_list.add(new Jewelry(631, 30));
_list.add(new Jewelry(198, 7));
_list.add(new Jewelry(317, 20));

_list = _list.stream().sorted(Comparator.comparing(Jewelry::get_cost_effective).reversed())
.collect(Collectors.toList());

for (int i = 1; i < 101; i++) {
System.out.println("n = " + i + " ,price = " + most_value(_list, i));
}

}

private static double most_value(List<Jewelry> _list, double n) {

if (_list.size() == 0 || _list.stream().min(Comparator.comparing(e -> e.weight)).get().weight > n) {
return 0;
}

List<Jewelry> _list_new = _list.stream().filter(e -> e.weight <= n).collect(Collectors.toList());
double global_solution = 0;

for (Jewelry item : _list_new) {

double solution =
item.price + most_value(_list_new.stream().filter(e -> e != item).collect(Collectors.toList()),
n - item.weight);
global_solution = Math.max(global_solution, solution);

}

return global_solution;

}

}

class Jewelry {

public final double price;
public final double weight;
public final double cost_effective;

public Jewelry(double price, double weight) {

this.price = price;
this.weight = weight;
this.cost_effective = price / weight;
}

public Double get_cost_effective() {

return cost_effective;
}

}



同上面個solution一樣answer,不過計埋性價比好似好無謂

:^(

洛托姆圖鑑 2017-3-20 13:41:50 就咁計都未識計

:^(

Zev92 2017-3-20 15:07:53

:^(

:^(

膠不可登 2017-3-20 21:33:32 每樣珠寶可以拎一件定多件?

例如n = 34:

每樣拎一件: D + C + F = 904
每樣拎多件: D + (F * 2) = 978

Angular 2017-3-20 22:56:22 珠寶是否必須整件拿走還是可以分割只拿部份也有很大影響

深夜情色園 2017-3-21 09:13:14

每樣珠寶可以拎一件定多件?

例如n = 34:

每樣拎一件: D + C + F = 904
每樣拎多件: D + (F * 2) = 978

每樣珠寶得一件

深夜情色園 2017-3-21 09:13:25

珠寶是否必須整件拿走還是可以分割只拿部份也有很大影響

不可切割

Lambda 2017-3-21 16:30:43 0 < n <= sum of weight of all jewelry ?