prolog購物籃（L，Smin，Smax，S）

-1

這裏有一個Prolog的問題。考慮一組產品，每個產品都有一個給定的價格。爲了簡單起見，我們考慮每種產品的一個項目。假設您有一個配對列表(Item,Price)，表示商店中商品的名稱及其對應的價格。該名稱是一個常數，價格是一個正整數。例如：prolog購物籃（L，Smin，Smax，S）

[(radio,130),(tv,940),(laptop,400),(bicycle,330)]

寫謂詞basket(L,Smin,Smax,S)是發現在L這樣可用的項目的子集S，在S價格的總和高於Smin和低於Smax。所有符合問題規範的可能子集都應該通過回溯逐個呈現！

來源

2016-01-06 user2953788

這是功課？你有什麼嘗試？ –

請顯示您嘗試過的內容。 – lurker

你好。關於[如何問作業問題]的文檔（http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions）說：「做一個誠信的嘗試如果我們看不到你方面有足夠的工作，你的問題很可能會被拋出舞臺，它會被拒絕並被關閉。「請張貼代碼。 –

在Prolog中，大部分時間減輕事情的做法是使用累加器。累加器是您遞歸傳遞並在每個遞歸步驟中更新的變量。每個遞歸步驟都可以檢查變量的值並據此作出決定。這裏的累加器就是這個項目的價格總和這個遠加到S。顯然，在一開始，即總和爲零，所以我們首先通過引入蓄電池緩解事情有點：

basket(L,Smin,Smax,S) :- 
    basket(L,Smin,Smax,0,S).

現在，我們需要制定出basket/5。有一個基礎案例，其中列舉了所有項目。因此L爲空。我們需要做的是什麼，是檢查是否Sum是指定的界限之間：

basket([],Smin,Smax,Sum,[]) :- 
    Smin < S, 
    S < Smax.

這是唯一的基本情況。請注意，S（最後一個參數）也是空列表。由於所有項目都已經過檢查，這意味着我們不會將任何元素添加到子集的尾部。

現在有兩個遞歸情況。在遞歸的情況下，L包含至少一個元素，我們可以做兩件事情：

我們要麼接受這個項目，並將其添加到我們的子集;
或我們丟棄該物品，並繼續進一步操作。

在我們接受這個項目的情況下，謂詞的樣子：

basket([(I,V)|T],Smin,Smax,Sum,[(I,V)|S]) :- 
    Sum1 is Sum+V, 
    Sum1 < Smax, 
    basket(T,Smin,Smax,Sum1,S).

因此，我們決定要添加的元素，我們通過添加值V原來的Sum計算新的總和Sum1，我們可以（可選）已經對值的上限執行邊界檢查。如果存在大量物品，這可以是有效的：我們的包從溢出時開始運行的那一刻起就停止了搜索。

最後，我們有另一個遞歸的情況下，我們只是決定放棄該項目。這是一個簡單的一個：

basket([_|T],Smin,Smax,Sum,S) :- 
    basket(T,Smin,Smax,Sum,S).

我們甚至不看頭，我們簡單地採取feeded到basket列表的尾部，我們沒有更新Sum，因爲沒有任何改變的子集。

全部放在一起，下面的程序應該做的伎倆：

basket(L,Smin,Smax,S) :- 
    basket(L,Smin,Smax,0,S). 

basket([],Smin,Smax,Sum,[]) :- 
    Smin < S, 
    S < Smax. 
basket([(I,V)|T],Smin,Smax,Sum,[(I,V)|S]) :- 
    Sum1 is Sum+V, 
    Sum1 < Smax, 
    basket(T,Smin,Smax,Sum1,S). 
basket([_|T],Smin,Smax,Sum,S) :- 
    basket(T,Smin,Smax,Sum,S).

不過請注意，使用動態編程一個可以更有效地生成解決方案的方式。

來源

2016-01-06 17:41:37

當我們子列表/ 2 this answer

sublist([], []). 
sublist([_|XS], YS) :- 
    sublist(XS, YS). 
sublist([X|XS], [X|YS]) :- 
    sublist(XS, YS).

庫（aggregate）可以用來強制約束：

basket(L,Smin,Smax,S) :- 
    sublist(L,S), 
    aggregate(sum(P), I^member((I,P),S), T), 
    T>=Smin,T=<Smax. 

?- basket([(radio,130),(tv,940),(laptop,400),(bicycle,330)],1600,2000,S). 
S = [(tv, 940), (laptop, 400), (bicycle, 330)] ; 
S = [(radio, 130), (tv, 940), (laptop, 400), (bicycle, 330)].

來源

2016-01-06 19:43:08 CapelliC

prolog購物籃（L，Smin，Smax，S）

回答

相關問題