問(wèn)答題

【計(jì)算題】當(dāng)n=7，m=15，（p1，.....p7）=（10，5，15，7，6，18，3）和（1w，.....w7）=（2，3，5，7，1，4，1）。將以上數(shù)據(jù)情況的背包問(wèn)題記為I。設(shè)FG（I）是物品按ip的非增次序輸入時(shí)由GREEDY-KNAPSACK所生成的解，F(xiàn)O（I）是一個(gè)最優(yōu)解。問(wèn)FO（I）/ FG（I）是多少？

答案：

你可能感興趣的試題

問(wèn)答題

【計(jì)算題】當(dāng)n=7，m=15，（p1，.....p7）=（10，5，15，7，6，18，3）和（1w，.....w7）=（2，3，5，7，1，4，1）。求背包問(wèn)題的最優(yōu)解。

答案：

問(wèn)答題

【簡(jiǎn)答題】什么是貪心方法？給出使用SPARKS語(yǔ)言描述的貪心方法的抽象化控制。

答案：對(duì)求取最優(yōu)解問(wèn)題，選取一種度量標(biāo)準(zhǔn)，將輸入按度量標(biāo)準(zhǔn)排序，并按此序一次輸入一個(gè)量。如果這個(gè)輸入和前面輸入產(chǎn)生的在這種度量...