1、問題（參考趣學算法）

 

央視有一個大型娛樂節目— 購物街,舞臺上模擬超市大賣場,有很多貨物,每個嘉賓分配一個購物車,可以盡情的裝滿購物車,購物車裝的價值最高者取勝。假設 n 個物品和 1個購物車,每個物品 i 對應價值為 vi,重量 wi,購物車的容量為 W(你也可以將重量設定為體積)。每個物品只有一件,要么裝入,要么不裝入,不可拆分。如何選取物品裝入購物車,使購物車所裝入的物品的總價值最大?要求輸出最優值(裝入的最大價值)和最優解(裝入了哪些物品)。 

 

 

2、分析

 

從 n 個物品中選擇一些物品,相當于從 n 個物品組成的集合 S 中找到一個子集,這個子集內所有物品的總重量不超過購物車容量,并且這些物品的總價值最大。S 的所有的子集都是問題的可能解,這些可能解組成了解空間,我們在解空間中找總重量不超過購物車容量且價值最大的物品集作為最優解 

1）、算法設計

 

(1)定義問題的解空間
購物車問題屬于典型的 0-1 背包問題,問題的解是從 n 個物品中選擇一些物品使其在不

超過容量的情況下價值最大。每個物品有且只有兩種狀態,要么裝入購物車,要不不裝入。那么第 i 個物品裝入購物車,能夠達到目標要求,還是不裝入購物車能夠達到目標要求呢?很顯然,目前還不確定。因此,可以用變量 xi 表示第 i 種物品是否被裝入購物車的行

總結

以上是生活随笔為你收集整理的回溯算法之购物车(0-1 背包问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。