題目描述
牛牛準備參加學校組織的春遊, 出發前牛牛準備往背包裡裝入一些零食, 牛牛的背包容量為w。
牛牛家裡一共有n袋零食, 第i袋零食體積為v[i]。
牛牛想知道在總體積不超過背包容量的情況下,他一共有多少種零食放法(總體積為0也算一種放法)。
輸入描述
輸入包括兩行
第一行為兩個正整數 n n n和 w ( 1 < = n < = 30 , 1 < = w < = 2 ∗ 1 0 9 ) w(1 <= n <= 30, 1 <= w <= 2 * 10^9) w(1<=n<=30,1<=w<=2∗109),表示零食的數量和背包的容量。
第二行 n n n個正整數 v [ i ] ( 0 < = v [ i ] < = 1 0 9 ) v[i](0 <= v[i] <= 10^9) v[i](0<=v[i]<=109),表示每袋零食的體積。
輸出描述
輸出一個正整數, 表示牛牛一共有多少種零食放法。
示例
輸入：
3 10
1 2 4
輸出：
8
解法一：暴力求解
N N N個零食就有 2 N 2^N 2N種防治方法，周遊這些放置方法，檢查哪些方法是有效的，時間複雜度為 O ( N ∗ 2 N ) O(N*2^N) O(N∗2N)，複雜度相當高，當然也沒有被ac。
這裡涉及到一個問題就是如何判斷方法是否有效，以示例為例來說，3個零食就有8中方法，1~4的二進制表示為：
1: 001 ---- 第一個零食放下
2: 010 ---- 第二個零食放下
3: 011 ---- 第一、二個零食被放下
4: 100 ---- 第三個零食放下
可以看到二進制表示中的每位上的1就代表了第幾個零食應該放下，是以我們隻需要去判斷放下這些零食是否會超出存儲空間即可。
if __name__ == '__main__':
n, w = map(int, input().split())
v = list(map(int, input().split()))
v_new = []
for i in v:
if i <= w:
v_new.append(i)
n = len(v_new)
total_num = 1<<n
res = 0
for i in range(total_num):
left = w
j = 0
while j < n and left >= 0:
if i & (1<<j):
left -= v[j]
j += 1
if left >= 0: res += 1
print(res)
解法二：中途相遇法
使用中途相遇法的思想，将 N N N份零食一分兩半，枚舉第一份的所有取法，用一個體積數組記錄體積和，再枚舉第二份的所有取法，從體積數組中找到大于等于
第二份體積的第一個位置，就是所有的取法。
if __name__ == '__main__':
import bisect
n, w = map(int, input().split())
v = list(map(int, input().split()))
v_new = []
for i in v:
if i <= w:
v_new.append(i)
n = len(v_new)
up = n // 2
down = n - n//2
space = []
res = 0
total_up = 1<<up
for i in range(total_up):
left = w
j = 0
while j < up and left >= 0:
if i & (1<<j):
left -= v[j]
j += 1
if left >= 0:
space.append(w-left)
space.sort()
total_down = 1<<down
for i in range(total_down):
left = w
j = 0
while j < down and left >= 0:
if i & (1<<j):
left -= v[j+up]
j += 1
if left >= 0:
# res = bisect.bisect_right(space, left) - space[0]
res += bisect.bisect_right(space, left)
print(res)
這裡需要說明一下為什麼res += bisect.bisect_right(space, left):
space數組中存儲的是第一份數組的存儲空間，而第二份數組的存儲空間在space中找到相應的位置就代表着有多少種取法。
解法三：深度搜尋法(DFS)
def dfs(idx, n, visited, count, left, v):
if idx == n:
return
for i in range(idx, n):
if not visited[i] and left >= v[i]: #目前點沒有被通路且存儲空間能夠裝下
visited[i] = True
count += 1
left -= v[i]
#繼續往後搜尋看是否有符合條件的點
dfs(i+1, n, visited, count, left, v)
visited[i] = False #釋放目前的點
left += v[i] #釋放存儲空間
if __name__ == '__main__':
n, w = map(int, input().split())
v = list(map(int, input().split()))
if sum(v) <= w:
print(1<<n)
else:
visited = [False]*n
count = 1
left = w
dfs(0, n, visited, count, left, v)
print(count)
其實這裡有個坑，就是count=[1]，如果count=1就會出錯，至今我也沒弄清楚這個bug的緣由。
此外，這裡也給出dfs的一個僞代碼：
/**
* DFS核心僞代碼
* 前置條件是visit數組全部設定成false
* @param n 目前開始搜尋的節點
* @param d 目前到達的深度，也即是路徑長度
* @return 是否有解
*/
bool DFS(Node n, int d){
if (d == 4){//路徑長度為傳回true，表示此次搜尋有解
return true;
}
for (Node nextNode in n){//周遊跟節點n相鄰的節點nextNode，
if (!visit[nextNode]){//未通路過的節點才能繼續搜尋
//例如搜尋到V1了，那麼V1要設定成已通路
visit[nextNode] = true;
//接下來要從V1開始繼續通路了，路徑長度當然要加
if (DFS(nextNode, d+1)){//如果搜尋出有解
//例如到了V6，找到解了，你必須一層一層遞歸的告訴上層已經找到解
return true;
}
//重新設定成未通路，因為它有可能出現在下一次搜尋的别的路徑中
visit[nextNode] = false;
}
//到這裡，發現本次搜尋還沒找到解，那就要從目前節點的下一個節點開始搜尋。
}
return false;//本次搜尋無解
![python解決最短路徑問題：Floyd-Warshall算法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)