瀹為獙 4 鐢ㄥ垎鏀�闄愮晫娉曞疄鐜�0-1鑳屽寘闂�棰� - 鐧惧害鏂囧簱

鏂板缓

涓婁紶

棣栭〉

鍔╂墜

鏈�杩?/div>

璧勬枡搴?/div>

宸ュ叿

 

瀹為獙鍥涚敤鍒嗘敮闄愮晫娉曞疄鐜?/p>

0-1

鑳屽寘闂�棰�

 

涓�锛庡疄楠岀洰鐨?/p>

 

1.

鐔熸倝鍒嗘敮闄愮晫娉曠殑鍩烘湰鍘熺悊銆?/p>

 

2.

閫氳繃鏈�娆″疄楠屽姞娣卞�瑰垎鏀�闄愮晫娉曠殑鐞嗚В銆?/p>

?? 

浜岋紟瀹為獙鍐呭�瑰強瑕佹�?/p>

 

鍐呭�癸�?/p>

.

缁欏畾

n

绉嶇墿鍝佸拰涓�涓�鑳屽寘銆傜墿鍝?/p>

i

鐨勯噸閲忔槸

w

锛屽叾浠峰�间负

v

锛岃儗鍖呭�归噺涓�

c

銆傞棶搴旇�ュ�備綍閫?/p>

鎷╄�呭叆鑳屽寘鐨勭墿鍝侊紝浣垮緱瑁呭叆鑳屽寘涓�鐗╁搧鐨勬�讳环鍊兼渶澶?/p>

? 

瑕佹眰锛?/p>

浣跨敤浼樺厛闃熷垪寮忓垎鏀�闄愮晫娉曠畻娉曠紪绋嬶紝姹傝�?/p>

0-1

鑳屽寘闂�棰�

 

涓夛紟绋嬪簭鍒楄〃

 

#include

<iostream>

 

#include

<stack>

 

usingnamespace

std; 

#define

N

100 

class

HeapNode

//

瀹氫箟

HeapNode

缁撶偣绫?/p>

 

{ 

public

: 

 

double

upper,price,weight;

//upper

涓虹粨鐐圭殑浠峰�间笂鐣岋紝

price

鏄�缁撶偣鎵�瀵瑰簲鐨勪环鍊硷紝

weight

涓虹粨鐐规墍鐩稿簲鐨勯噸閲?/p>

 

 

int

level,x[

N

];

//

娲昏妭鐐瑰湪瀛愰泦鏍戜腑鎵�澶勭殑灞傚簭鍙?/p>

 

}; 

double

MaxBound(

int

i); 

double

Knap(); 

void

AddLiveNode(

double

up,

double

cp,

double

cw,

bool

ch,

int

level);

//up

鏄�浠峰�间笂鐣岋紝

cp

鏄�鐩稿簲鐨勪环鍊硷紝

cw

鏄�璇ョ粨鐐规墍鐩?/p>

搴旂殑閲嶉噺锛?/p>

ch

鏄?/p>

tureorfalse

 

stack

<

HeapNode

>High;

//

鏈�澶ч槦

High

 

double

w[

N

],p[

N

];

//

鎶婄墿鍝侀噸閲忓拰浠峰�煎畾涔変负鍙岀簿搴︽诞鐐规暟