背包问题的算法 0-1背包问题用什么实现算法最好
\u80cc\u5305\u95ee\u9898\u7b97\u6cd5\u9996\u5148\u5efa\u7acb\u4e00\u4e2a\u5806\u6808\uff0c\u91cc\u9762\u5b58\u653e\u7684\u662f\u7269\u54c1\u4fe1\u606f\u3002\u7b97\u6cd5\u5f00\u59cb\u540e\uff0c\u6309\u7167\u4e00\u5b9a\u7684\u6b21\u5e8f\u5b58\u653e\u7269\u54c1\uff0c\u6bcf\u653e\u8fdb\u53bb\u4e00\u4e2a\u7269\u54c1\uff0c\u5c31\u68c0\u67e5\u662f\u5426\u8d8a\u754c\uff0c\u5982\u679c\u6ca1\u8d8a\u754c\uff0c\u5c31\u7ee7\u7eed\u9009\u62e9\u7269\u54c1\u653e\u5165\uff08\u5165\u6808\uff09\uff1b\u5982\u679c\u8d8a\u754c\uff0c\u5c31\u9000\u51fa\u5f53\u524d\u7269\u54c1\uff08\u51fa\u6808\uff09\uff0c\u5f53\u6b63\u597d\u88c5\u6ee1\u4e00\u4e2a\u80cc\u5305\u65f6\uff0c\u8bb0\u5f55\u5f53\u524d\u6808\u5230\u4e00\u4e2a\u6570\u7ec4\uff0c\u5e76\u9000\u51fa\u9876\u7aef\u7269\u54c1\uff08\u51fa\u6808\uff09\uff0c\u5f80\u540e\u653e\u7269\u54c1\u2026\u2026\u4e00\u76f4\u5230\u6808\u7a7a\u4e3a\u6b62\uff0c\u8fd9\u6837\u53ef\u4ee5\u627e\u5230\u6240\u6709\u6700\u4f73\u5b58\u653e\u65b9\u6cd5\u3002
\u6211\u4eec\u4e66\u4e0a\u7ed9\u76840-1\u80cc\u5305\u95ee\u9898\u662f\u662f\u7528\u52a8\u6001\u89c4\u5212\u65b9\u6cd5\u505a\u7684\u8fd9\u4e2a\u7b97\u6cd5\u662f\u52a8\u6001\u89c4\u5212\u7684\u5178\u578b\u5e94\u7528\u6240\u4ee5\u4f60\u628a\u52a8\u6001\u89c4\u5212\u7684\u601d\u60f3\u641e\u6e05\u695a\u5c31\u5e94\u8be5\u53ef\u4ee5\u7406\u89e3\u4e86\u4e0b\u9762\u6211\u628a\u52a8\u6001\u89c4\u5212\u7684\u601d\u60f3\u7ed9\u4f60\u8bf4\u4e00\u4e0b,\u5e0c\u671b\u5bf9\u4f60\u6709\u6240\u5e2e\u52a9.\u54e6..\u4e0d\u597d\u610f\u601d..\u65f6\u95f4\u4e0d\u591a\u4e86..\u4f60\u81ea\u5df1\u5230\u7f51\u4e0a\u627e\u4e00\u4e0b\u8fd9\u65b9\u9762\u7684\u601d\u60f3..\u7136\u540e\u7ed3\u5408\u4e00\u4e2a\u5b9e\u4f8b\u8ba4\u771f\u7814\u8bfb\u4e00\u4e0b..\u5f04\u61c2\u4e4b\u540e..\u4f60\u5bf9\u52a8\u6001\u89c4\u5212..0-1\u80cc\u5305\u95ee\u9898\u5c31\u4f1a\u6709\u6bd4\u8f83\u6df1\u5165\u7684\u7406\u89e3.\u5efa\u8bae\u597d\u597d\u5b66\u4e00\u4e0b\u7b97\u6cd5..\u8fd9\u5bf9\u8ba1\u7b97\u673a\u4e13\u4e1a\u5b66\u751f\u6765\u8bf4\u5f88\u91cd\u8981..\u6211\u8d8a\u6765\u8d8a\u89c9\u5f97\u795d\u5b66\u6709\u6240\u6210
3.2 背包问题背包问题有三种
1.部分背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。
解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.
2.0/1背包
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。
<1>分析说明:
显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).
程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数
设 f(i，x)表示前i件物品，总重量不超过x的最优价值
则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））
f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;
动态规划方法(顺推法)程序如下:
程序如下：
program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;
for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.
使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。
3.完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n
程序如下:（顺推法）
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.
绛旓細鍒╃敤浼樺厛绾у垎鏀檺鐣屾硶璁捐0/1鑳屽寘闂鐨勭畻娉锛屾帉鎻″垎鏀檺鐣屾硶鐨勫熀鏈濇兂鍜岀畻娉曡璁＄殑鍩烘湰姝ラ锛屾敞鎰忓叾涓粨鐐逛紭鍏堢骇鐨勭‘瀹氭柟娉曪紝瑕佹湁鍒╀簬鎵惧埌鏈浼樿В鐨勫惎鍙戜俊鎭傝姹傦細璁捐0/1鑳屽寘闂鐨勫垎鏀檺鐣岀畻娉曪紝鍒╃敤c璇█锛坈++璇█锛夊疄鐜扮畻娉曪紝缁欏嚭绋嬪簭鐨勬纭繍琛岀粨鏋溿傛敞鎰忥細1. 鎶婄墿鍝佹寜鐓у崟浣嶄綋绉殑浠峰奸檷搴忔帓鍒楋紱2...
绛旓細鈥撹椽蹇冿細姣忎釜闃舵浜х敓鐨勯兘鏄眬閮ㄦ渶浼樿В •绗琲闃舵鐨勨滃眬閮ㄢ濓細闂绌洪棿涓烘寜鐓ц椽蹇冪瓥鐣ヤ腑鐨勪紭鍏堢骇鎺掑ソ搴忕殑绗琲涓緭鍏i •绗琲闃舵鐨勨滃眬閮ㄦ渶浼樿В鈥濓細 ai •璐績閫夋嫨鎬ц川锛氭墍姹闂鐨鍏ㄥ眬鏈浼樿В鍙互閫氳繃涓绯诲垪灞閮ㄦ渶浼樼殑閫夋嫨锛堝嵆璐績閫夋嫨锛夋潵杈惧埌銆傗撹繖鏄椽蹇绠楁硶涓庡姩鎬佽鍒掔畻娉曠殑...
绛旓細鍏锋湁鑹ソ鐨勫苟琛屾э紝鑰屼笖閬椾紶绠楁硶鍙渶鍒╃敤鐩爣鐨勫彇鍊间俊鎭,鑰屾棤闇閫掑害绛夐珮浠峰间俊鎭,鍥犳閫傜敤浜庝换浣曡妯°傞仐浼犵畻娉曠殑楂樺害闈炵嚎褰㈢殑涓嶈繛缁宄板嚱鏁扮殑浼樺寲浠ュ強鏃犺В鏋愯〃杈惧紡鐨勭洰鏍囧嚱鏁扮殑浼樺寲,鍏锋湁寰堝己鐨勯氱敤鎬с傦紙濡傛灉浣犳槸闇瑕佽绠楁満缂栫▼搴忕殑璇濓紝绛旀鍐呭灏辨洿澶氫簺锛岀幇鍦ㄤ笉鏅撳緱浣犲簲鐢鑳屽寘闂鍋氫粈涔堝憿锛...
绛旓細锛4锛夎椽蹇冪畻娉曡В鍐鑳屽寘闂鐨勭畻娉瀹炵幇锛氫唬鐮佸涓嬶細include <iostream.h> struct goodinfo { float p; //鐗╁搧鏁堢泭 float w; //鐗╁搧閲嶉噺 float X; //鐗╁搧璇ユ斁鐨勬暟閲 int flag; //鐗╁搧缂栧彿 };//鐗╁搧淇℃伅缁撴瀯浣 void Insertionsort(goodinfo goods[],int n) {//鎻掑叆...
绛旓細闂鎻忚堪锛 缁欏畾n绉嶇墿鍝佸拰涓鑳屽寘锛岀墿鍝乮鐨勯噸閲忔槸wi锛屽叾浠峰间负vi锛岃儗鍖呯殑瀹归噺涓篊銆傞棶搴斿浣曢夋嫨瑁呭叆鑳屽寘鐨勭墿鍝侊紙鐗╁搧涓嶈兘鍒嗗壊锛夛紝浣垮緱瑁呭叆鑳屽寘涓墿鍝佺殑鎬讳环鍊兼渶澶?鎶借薄鎻忚堪濡備笅锛 x[n]:琛ㄧず鐗╁搧鐨勯夋嫨锛寈[i]=1琛ㄧず閫夋嫨鏀捐繘鐗╁搧i鍒拌儗鍖呬腑銆傞棶棰樺垎鏋愶細 1.鎶借薄涔嬪悗鑳屽寘闂杞崲涓烘壘鍒颁竴涓渶...
绛旓細绠楁硶鍒嗘瀽锛氫娇鐢ㄨ椽蹇冪瓥鐣ユ眰瑙ｆ绫婚棶棰樻椂锛岄鍏堣閫夊嚭鏈浼樼殑搴﹂噺鏍囧噯銆傚彲渚涢夋嫨鐨勫害閲忔爣鍑嗘湁涓夌锛氫环鍊硷紝瀹归噺锛屽崟浣嶄环鍊硷紙v/w锛屼环鍊/閲嶉噺锛夈傛樉鐒讹紝浠峰奸珮鐨勭墿鍝佸閲忓彲鑳藉お澶э紝瀹归噺澶х殑鐗╁搧浠峰间篃鍙兘寰堜綆銆傛渶浼樼殑搴﹂噺鏍囧噯鏄崟浣嶄环鍊笺鑳屽寘闂绠楁硶鎬濊矾锛1銆佸皢鍚勪釜鐗╁搧鎸夌収鍗曚綅浠峰肩敱楂樺埌浣庢帓搴忥紱2銆佸彇浠峰...
绛旓細p(i) / w(i)=( 2/7, 4/3, 3/5, 5/6, 7/8 ,4, 6/5)x(i)=(1, 1, 0 ,0 ,1 ,1 ,1)锛堟眰鍜屽叕寮忥級w(i)x(i0=35*1+30*1+50*0+60*0+40*1+10*1+25*1=140 (姹傚拰鍏紡)p(i)x(i)=10*1+40*1+30*0+50*0+35*1+40*1+30*1=155 鍗鑳屽寘鐨鏈浼樿В...
绛旓細3)璐┆绠楁硶鏀硅繘鐨鑳屽寘闂:缁欏畾涓涓秴閫掑搴忓垪鍜屼竴涓儗鍖呯殑瀹归噺,鐒跺悗鍦ㄨ秴閫掑搴忓垪涓(鍙兘閫変竴娆)鎴栦笉閫夋瘡涓涓暟鍊,浣垮緱閫変腑鐨勬暟鍊肩殑鍜屾濂界瓑浜庤儗鍖呯殑瀹归噺銆備唬鐮佹濊矾:浠庢渶澶х殑鍏冪礌寮濮嬮亶鍘嗚秴閫掑搴忓垪涓殑姣忎釜鍏冪礌,鑻ヨ儗鍖呰繕鏈夊ぇ浜庢垨绛変簬褰撳墠鍏冪礌鍊肩殑绌洪棿,鍒欐斁鍏,鐒跺悗缁х画鍒ゆ柇涓嬩竴涓厓绱;鑻ヨ儗鍖呭墿浣欑┖闂村皬浜庡綋鍓嶅厓绱...
绛旓細dp(i,j)琛ㄧず鍓峣浠剁墿鍝侀夋嫨浠绘剰浠跺悗鏀捐繘鏈澶у閲忎负j鐨鑳屽寘鐨鏈澶т环鍊笺傛樉鐒讹紝dp(0,j)=0锛宒p(i,0)=0銆傚浜庣i浠剁墿鍝侊紝鏈変袱绉嶆儏鍐碉細涓銆佷笉鏀捐繘鑳屽寘锛屽垯鏈澶т环鍊间负鍓峣-1浠剁墿鍝佸彲浠ユ斁杩涘閲忎负j鐨勮儗鍖呯殑鏈澶т环鍊硷紝鍗砫p(i,j)=dp(i-1,j)浜屻佹斁杩涜儗鍖咃紝鍒欐渶澶т环鍊间负绗琲浠剁墿鍝佷环鍊煎姞涓婂墠...
绛旓細杈撳叆锛歴 鑳屽寘鐨浣撶Н n 鐗╁搧鐨勬暟閲 w[] 姣忎欢鐗╁搧鐨勪綋绉 杈撳嚭锛氳嫢瀛樺湪鑷冲皯涓绉嶅垰濂借婊¤儗鍖呯殑鏂瑰紡锛屽垯杈撳嚭杩欑鏂瑰紡锛涜嫢涓嶅瓨鍦紝鍒欒緭鍑簄o solution 璇绠楁硶浣跨敤閫掑綊鍑芥暟knap銆傝鍑芥暟棣栧厛灏濊瘯灏嗘渶鍚庝竴浠剁墿鍝佹斁鍏ヨ儗鍖咃紝鍒欑墿鍝佸噺灏戜竴浠讹紝鑳屽寘鍙敤浣撶Н鐩稿簲鍑忓皯锛岀劧鍚庡褰撳墠鐘舵佽繘琛岄掑綊鈥︹﹁嫢鏈夎В鍒欓掑綊缁撴潫锛涜嫢...
