0/1背包問題：有n個重量分別為w1莫湘、w2、…郑气、wn的物品（物品編號為1~n）幅垮，他們的價值分別為v1、v2尾组、…忙芒、vn，給定義給定一個容量為W的背包讳侨。設(shè)計從這些物品中選取一部分物品放入該背包的方案呵萨，每個物品要么選中要么不選中，要求選中的物品不僅能夠放到背包中跨跨，而且具有最大的價值潮峦。求出所有的物品組合，對于每一種組合勇婴，計算其總重量sumw和總價值sumv忱嘹，當(dāng)sumw小于等于W時該組合是一種解，并通過比較將最佳方案保存到maxsumw和maxsumv中耕渴，最后輸出最佳解拘悦。
用回溯法求解：用x[1..n]數(shù)組存放最優(yōu)解，x[i]=1表示第i個物品放入背包中橱脸，x[i]=0表示第i個物品不放入背包中础米。由于每個物品要么裝入，要么不裝入慰技，其解空間是一顆子集數(shù)椭盏，樹中每個節(jié)點表示背包的一種選擇狀態(tài)，記錄當(dāng)前放入背包的物品總重量和總價值吻商，每個分支節(jié)點下面由兩邊表示對物品是否放入背包的兩種可能的選擇掏颊。對第i層上的某個分支節(jié)點，對應(yīng)的狀態(tài)為dfs(i,tw,tv,op)，其中tw表示裝入背包中的物品總重量乌叶，tv表示背包中物品總價值盆偿，op記錄一個解向量。該狀態(tài)的兩種擴(kuò)展如下：
[if !supportLists]（1）??[endif]選擇第i個物品放入背包：op[i]=1准浴，tw=tw+w[i]事扭，tv=tv+v[i]，轉(zhuǎn)向下一個狀態(tài)des(i+1,tw,tv,op)乐横。該決策對應(yīng)左分支求橄。
[if !supportLists]（2）??[endif]不選擇第i個物品放入背包：op[i]=0，tw不變葡公，tv不變罐农，轉(zhuǎn)向下一個狀態(tài)dfs(i+1,tw,tv,op)。該決策對應(yīng)右分支催什。
對所有葉子結(jié)點進(jìn)行比較求出滿足tw=W的最大價值maxv涵亏，對應(yīng)的最優(yōu)解op存放到x中。
