우리는 배낭 문제의 작은 인스턴스를 해결 엑셀 VBA에서 프로그램을보고 아래.

정의 : 총 값은 가능한 한 크게하고 총 중량을 적게 소정 한도를 초과하도록 항목 세트, 중량 및 값 각 집합에 포함시킬 항목을 결정 주어.

그것은 고정 된 크기의 배낭에 의해 제약되고 가장 유용한 항목을 작성해야합니다 사람이 직면 한 문제에서 자사의 이름을 파생합니다.

예 : 무게, 가치와 한계 5 개 항목 주어진.

Knapsack Problem Image

Excel에서이 문제는 보이는 다음과

Knapsack Problem Example

  1. 먼저, 우리는 이름 제한, 체중, 가치, totalWeight 및 maximumValue와 유형을 두 번 다섯 개 가지 변수를 선언합니다.

Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double

  1. 다음으로, 우리는 이름 I, J, K, L, m과 타이핑 정수 다섯 개 변수를 선언.

Dim i, j, k, l, m As Integer

  1. 우리는 두 개의 변수를 초기화합니다. 우리는 셀 D6의 값으로 변수 제한을 초기화합니다. 우리는 값이 0으로 변수 maximumValue를 초기화

limit = Range("D6").value

maximumValue = 0

  1. 다음으로, 우리는 각각의 가능한 솔루션을 확인한다. 우리는 하나의 항목 (1)을 포함하거나 (0)을 생략 할 수 있습니다. 우리는 다음 루프를 들어 5를 시작합니다. 각 항목에 대해 하나.

For i = 0 To 1

For j = 0 To 1

For k = 0 To 1

For l = 0 To 1

For m = 0 To 1

  1. 우리는 중량 및 가능한 솔루션의 값을 계산한다.

weight = 12  i + 2  j + 1  k + 1  l + 4  m

value = 4  i + 2  j + 2  k + 1  l + 10  m

값이 maximumValue보다 높은 무게 한계보다 낮은 경우에만 6. 우리는 새로운 더 나은 솔루션을 찾았습니다.

If value > maximumValue And weight <= limit Then

  1. true의 경우, 우리는 maximumValue에 새 totalWeight에 4 행, 무게 솔루션과 가치를 작성합니다.

Range("B4").value = i

Range("C4").value = j

Range("D4").value = k

Range("E4").value = l

Range("F4").value = m

totalWeight = weight

maximumValue = value

  1. 만약 문을 닫을 것을 잊지 마십시오.

End If

  1. 다음 루프를 들어 5를 종료하는 것을 잊지 마십시오.

Next m

Next l

Next k

Next j

Next i

엑셀 VBA 수표 각각의 가능한 솔루션을 최적의 솔루션을 기억 행 4에 우리는 우리가 그것을두고 항목, 0 수단을 포함 한 수단을 나타납니다 결과로 이런 식으로합니다.

  1. 마지막으로, 각각의 셀 B6 및 B8에 최적의 솔루션과 totalWeight maximumValue 물품.

Range("B6").value = totalWeight

Range("B8").value = maximumValue

  1. 시험 프로그램.

결과 :

Knapsack Problem Result

결론 : 그것의 최적 15. 2 + 1 + 1 + 4 = 8 (15)의 한계를 초과하지 않는

합계 중량이 용액의 최대 값이 마지막 네 개의 항목을 포함하는 참고 :이 크기의 배낭 문제를 해결할 수있는 무게와 값 변수를 만들어 (다운로드 Excel 파일 참조).