資源簡介
問題描述：
假設(shè)有一個能裝入總體積為T的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + … + wn=T，要求找出所有滿足上述條件的解。例如：當(dāng)T=10，各件物品的體積{1，8，4，3，5，2}時，可找到下列4組解：
（1，4，3，2）
（1，4，5）
（8，2）
（3，5，2）。
問題提示：
可利用回溯法的設(shè)計思想來解決背包問題。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如
代碼片段和文件信息
#include
#include
int?knap（int?s?int?n?int?w[]）?{
????if?（?s?==?0?）
????????return?（1）;
????else?if?（?s<0?||?s>0?&&?n<1?）
????????return（0）;
????else?if?（?knap（s?-?w[n-1]?n?-?1?w）==1?）?{?
????????printf（“result:?n=%d?w[%d]=%d??\n“?n?n-1?w[n-1]）;
????????return?（1）;
????}
????else
????????return?（?knap（s?n?-?1?w）?）;
}
int?main（）?{
????int*?w;
????int?s?=?0?n?=?0?result?=?0?i?=?0;
????printf（“please??input?s?=?“）;/*輸入s*/
????scanf（“%d“?&s）;
????printf（“please??input?n?=?“）;/*輸入n*/
????scanf（“%d“?&n）;
????w?=?（int*）malloc（n*sizeof（int））;
????printf（“please?input?the?%d?numbers（weight）:\n“?n）;/*輸入重量*/
????for?（i?=?0;?i?????????scanf（“%d“?w+i）;
????result?=?knap（s?n?w）;
????if?（result?==?0）
????????printf（“no?solutio?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????1424??2011-06-22?14:21??Cpp1.cpp
?????文件???????1256??2011-06-22?14:05??數(shù)組.cpp
?????文件???????1513??2011-06-22?14:29??a5.cpp
?????文件???????3324??2011-06-23?01:04??a55.cpp
?????文件????????833??2011-06-22?14:48??a.cpp
-----------?---------??----------?-----??----
?????????????????8350????????????????????5
評論
共有 條評論