淘寶的“雙十一”購(gòu)物節(jié)有各種促銷(xiāo)活動(dòng)，比如“滿 200 元減 50 元”。假設(shè)你的購(gòu)物車(chē)中有 n 個(gè)（n>100）想買(mǎi)的商品，希望從里面選幾個(gè)，在湊夠滿減條件的前提下，讓選出來(lái)的商品價(jià)格總和最大程度地接近滿減條件（200 元），這樣就可以極大限度地“薅羊毛”。

回溯法

我們假設(shè)購(gòu)物滿w元才能減。例如滿500減200，那w=500。購(gòu)物車(chē)中商品的價(jià)格int[] price表示。每次決定第i個(gè)物品要不要購(gòu)買(mǎi)，當(dāng)物品選完了或者總價(jià)夠w，停止選擇。比較選中物品價(jià)格總和最低的一組選擇。這是一個(gè)多階段決策最優(yōu)化問(wèn)題。可以先用回溯算法解決。

public class Shopping {private int[] price = new int[]{198,201,345,200};private int w = 500;private int minPrice = Integer.MAX_VALUE;private List<Integer> selectItems;private void f (int i,int priceSum,boolean[] shoppingStatus){if(priceSum>w){if(priceSum<minPrice){minPrice = priceSum;selectItems = new ArrayList<Integer>();for(int j=0;j<shoppingStatus.length;j++){if(shoppingStatus[j]){selectItems.add(j);}}}return;}if(i==price.length) return;shoppingStatus[i] = true;f(i+1,priceSum+price[i],shoppingStatus);//選擇第i件商品shoppingStatus[i] = false;f(i+1,priceSum,shoppingStatus);//不選擇第i件商品}public void decision(){boolean[] shoppingStatus = new boolean[price.length];f(0,0,shoppingStatus);} }

遞歸樹(shù)

遞歸樹(shù)中的每個(gè)節(jié)點(diǎn)是一個(gè)狀態(tài)，用(i,preSum)表示。i表示將要處理第i個(gè)商品。preSum表示當(dāng)前狀態(tài)下已經(jīng)購(gòu)買(mǎi)商品的價(jià)格和。可以看到這里的狀態(tài)表示的參數(shù)基本和f函數(shù)的參數(shù)是相同的。
在這個(gè)例子中，(i,preSum)相同的節(jié)點(diǎn)正好都只有一個(gè)，但不排除有多個(gè)節(jié)點(diǎn)的可能性。

狀態(tài)表

根據(jù)(i,preSum)我們知道用一個(gè)二維表可以表示各種不同的狀態(tài)。第一維（行）是商品下標(biāo)，第二維（列）是商品總價(jià)。又因?yàn)轭}目要求價(jià)格和需要大于w，但我們又不能讓商品和太大，太大優(yōu)惠就沒(méi)有必要了。我們需要給商品總價(jià)一個(gè)最大值3w。

狀態(tài)表boolean[][] states。
第0個(gè)商品決策之后，states[0][0]=true；states[0][198]=true。
第1個(gè)商品決策之后，states[1][0]=true；states[1][201]=true；states[1][198]=true；states[1][399]=true；
…

我們?cè)趕tates[n-1]從下標(biāo)w開(kāi)始找值為true的元素下標(biāo)。最先找到的就是符合要求的最小價(jià)格。
它與萊文斯坦距離、矩陣中的最短路徑長(zhǎng)度不同的地方是，不需要在每一步?jīng)Q策之后只保留最小值，其他節(jié)點(diǎn)放棄。
我想這里沒(méi)有放棄其他節(jié)點(diǎn)，是因?yàn)檫@里的每一個(gè)狀態(tài)可能就是最終答案。第i個(gè)商品是不是購(gòu)買(mǎi)，和第i-1個(gè)商品決策之后的所有狀態(tài)有關(guān)系。

public void decisionDp(){int n = price.length;int maxw = 3*w;boolean[][] states = new boolean[n][maxw+1];states[0][0] = true;if(price[0]<maxw){states[0][price[0]] = true;}for(int i=1;i<n;i++){//不購(gòu)買(mǎi)第i個(gè)for(int j=0;j<maxw+1;j++){if(states[i-1][j]){states[i][j] = true;}}//購(gòu)買(mǎi)第i個(gè)for(int j = 0;j<maxw+1;j++){if(states[i-1][j]==true && j+price[i]<maxw){states[i][j+price[i]] = true;}}}int minPrice = -1;for(int j = w;j<maxw+1;j++){if(states[n-1][j]){minPrice = j;break;}}//說(shuō)明有選擇if(minPrice!=-1){System.out.println(minPrice);int j = minPrice;for(int i=n-1;i>=1;i--){if(j-price[i]>=0 && states[i-1][j-price[i]]){System.out.println(price[i]);//購(gòu)買(mǎi)這件商品}}if(j!=0){System.out.println(price[0]);}}}

當(dāng)然，這道題目還要一個(gè)難點(diǎn)是要輸出選擇了哪些商品。當(dāng)我們知道滿足要求的最低總價(jià)是minPrice。也就是說(shuō)states[n-1][minPrice]=true。如果states[n-2][minPrice]=true，則說(shuō)明第n-1號(hào)物品是被放棄的，不購(gòu)買(mǎi)的。如果states[n-2][minPrice-price[n-1]]=true，說(shuō)明是購(gòu)買(mǎi)第n-1號(hào)商品的。繼續(xù)遞歸往回查找。

總結(jié)

以上是生活随笔為你收集整理的动态规划——双11既可以薅羊毛还能花钱最少的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。