好耐冇開過programming post！

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

不可切割

可以切就greedy搞掂

0 < n <= sum of weight of all jewelry ?

no

有冇人用基因演算法寫答案比小弟見識下

有冇人用基因演算法寫答案比小弟見識下

一條binary chromosome 就搞得掂？ 每粒gene 係一粒 Jewellery

有冇人用基因演算法寫答案比小弟見識下

其實基因演算法效果好差

有冇人用基因演算法寫答案比小弟見識下

用pso好過用ga啦，不如呢題唔需要

依條諗落去有d似玩network graph
利申，未睇solution

btw, 其實我係留名學習

<?php

$productList = array(
'A' => array(
'price' => 163,
'weight' => 12
),
'B' => array(
'price' => 221,
'weight' => 31
),
'C' => array(
'price' => 124,
'weight' => 5
),
'D' => array(
'price' => 582,
'weight' => 20
),
'E' => array(
'price' => 631,
'weight' => 30
),
'F' => array(
'price' => 198,
'weight' => 7
),
'G' => array(
'price' => 317,
'weight' => 20
)
);

for ($i = 0; $i <= 100; $i++)
{
list($maxPrice, $resultList) = getMaxPriceListByWeight($productList, $i);
print "When weight = $i, maxPrice = $maxPrice (".implode(', ', $resultList).")\n";
}

function getMaxPriceListByWeight($productList, $weightLimit)
{
$productCount = count($productList);
$maxPrice = 0;
$keyList = array_keys($productList);
$resultList = array();

for ($i = 0; $i < $productCount; $i++)
{
for ($j = 0; $j < $productCount; $j++)
{
if ($i == $j) continue;
$keyTemp = $keyList[$i];
$keyList[$i] = $keyList[$j];
$keyList[$j] = $keyTemp;
$totalPrice = 0;
$totalWeight = 0;

for ($k = 0; $k < $productCount; $k++)
{
if (($totalWeight + $productList[$keyList[$k]]['weight']) <= $weightLimit)
{
$totalPrice += $productList[$keyList[$k]]['price'];
$totalWeight += $productList[$keyList[$k]]['weight'];
} else
break;
}

if ($totalPrice > $maxPrice)
{
$maxPrice = $totalPrice;
$resultList = array_slice($keyList, 0, $k);
}
}
}

return array($maxPrice, $resultList);
}

?>

我用Bubble Sort慨念做, 不停swap個array element去test唔同combination

#include <cstdio>

int M = 7;
int price[] = {163, 221, 124, 582, 631, 198, 317};
int weight[] = {12, 31, 5, 20, 30, 7, 20};

int ans = 0;

void doit(int i, int total_price, int total_weight, int max_weight) {
if (total_weight > max_weight) {
return;
}
if (i == M) {
if (total_price > ans) {
ans = total_price;
}
return;
}
doit(i + 1, total_price, total_weight, max_weight);
doit(i + 1, total_price + price[i], total_weight + weight[i], max_weight);
}

int main() {
for (int n = 0; n <= 100; ++n) {
ans = 0;
doit(0, 0, 0, n);
printf("when n = %d, max price = %d\n", n, ans);
}
return 0;
}

簡簡單單, recursion

用greedy咪算囉呢D
簡簡單單

用greedy咪算囉呢D
簡簡單單

點解講得出Greedy但唔知Greedy唔係所有情況都有最佳解
而偏偏呢條題目就係唔能夠用Greedy要用DP解

用greedy咪算囉呢D
簡簡單單

點解講得出Greedy但唔知Greedy唔係所有情況都有最佳解
而偏偏呢條題目就係唔能夠用Greedy要用DP解

呢D問題根本冇best solution wo...

留名

用greedy咪算囉呢D
簡簡單單

點解講得出Greedy但唔知Greedy唔係所有情況都有最佳解
而偏偏呢條題目就係唔能夠用Greedy要用DP解

呢D問題根本冇best solution wo...

咩叫best solution...
如果你話optimal solution既話就一定有

用greedy咪算囉呢D
簡簡單單

點解講得出Greedy但唔知Greedy唔係所有情況都有最佳解
而偏偏呢條題目就係唔能夠用Greedy要用DP解

呢D問題根本冇best solution wo...

solution 首先要 correct，
然後可以再分析佢嘅 complexity，
Time Complexity -> 有幾快？
Space Complexity -> 要幾多記憶體？

https://en.wikipedia.org/wiki/Big_O_notation

以 recursion 的 solution 黎講，假設有 N 粒寶石，
Time Complexity -> O(2^N)
Space Complexity -> O (N)

以 DP 的 solution 黎講，假設有 N 粒寶石，重量的 range 係 0 到 M，
Time Complexity -> O(N * M)
Space Complexity -> O(N * M)

用greedy咪算囉呢D
簡簡單單

點解講得出Greedy但唔知Greedy唔係所有情況都有最佳解
而偏偏呢條題目就係唔能夠用Greedy要用DP解

呢D問題根本冇best solution wo...

solution 首先要 correct，
然後可以再分析佢嘅 complexity，
Time Complexity -> 有幾快？
Space Complexity -> 要幾多記憶體？

https://en.wikipedia.org/wiki/Big_O_notation

以 recursion 的 solution 黎講，假設有 N 粒寶石，
Time Complexity -> O(2^N)
Space Complexity -> O (N)

以 DP 的 solution 黎講，假設有 N 粒寶石，重量的 range 係 0 到 M，
Time Complexity -> O(N * M)
Space Complexity -> O(N * M)

其實problem-solving strategy層面兩種都係DP
只係top down定buttom-up既分別
recursion, memorization, tabulation係技術手段