방법

Question

0 ~ 1 배낭 문제로서는

,

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 

는 는 [i]는 i 번째 상품의 가격을 의미

C는 w 가 [I]의 값을 의미 0 ~ 1 배낭에 시간 복잡도를 감소 대한 이해 상품.

그리고 V는 무슨 뜻

i=1...N 

v=V...0 

아래 larger.as이

i=1...n   

bound=max{V-sum{w[i..n]},c[i]}   

v=V...bound 

로 변경 될 수있다 특히, 시간 복잡도가 최적화 될 수 있다고 말했다 하나의 문서를 읽어? V (가방의 최대 값)에서 w [i] (상품의 가치)의 합계를 뺀 값은 어떻게됩니까?

정말 혼동 스럽거나이 문서에 문제가 있습니까?

Answer 1

복잡성을 최적화한다고 말하지 않았습니다. 동적 프로그래밍을 사용하고 있습니까? 그렇다면 작은 값 v에 대해 f[i][v]을 계산할 필요가 없다는 것을 의미 할 수 있습니다. 왜냐하면 최적 값을 찾기 위해 값을 필요로하지 않기 때문입니다. 당신이 그보다 작은 용량 (제품 1..i로 제한)가 하위 문제 i를 해결하기 위해 필요가 없습니다

당신이 배낭에 i + 1에서 n 모든 물건을 넣을 경우에도, V - sum{c[i+1..n]} 왼쪽의 능력을 가지고 .

좀 더 공식적인 대답이 필요한 경우 자세한 내용과 함께 사용중인 알고리즘과 함께 문제를 설명하십시오.