포물선 배낭

포물선 배낭

---

포물선이 있다고 가정 해 봅시다. 이제 나는 또한 모두 같은 너비의 막대기를 가지고 있습니다 (예, 제 그리기 기술은 놀랍습니다!). 가능한 한 많이 사용하는 공간을 최소화하기 위해 포물선 안에 이러한 스틱을 쌓을 수 있습니까? 나는 이것이 Knapsack 문제 의 범주에 속한다고 생각 하지만,이 Wikipedia 페이지는 나를 현실 세계의 해결책에 더 가까이 가져다주지 않는 것 같습니다. 이것은 NP-Hard 문제입니까?

이 문제에서 우리는 수직 영역을 포함하여 소비되는 영역의 양 (예 : 적분)을 최소화하려고합니다.

---

processing.js 및 HTML5 캔버스를 사용하여 JavaScript로 솔루션을 만들었습니다 .

이 프로젝트는 자신 만의 솔루션을 만들고 싶다면 좋은 출발점이 될 것입니다. 두 가지 알고리즘을 추가했습니다. 하나는 입력 블록을 가장 큰 것에서 가장 작은 것까지 정렬하고 다른 하나는 목록을 무작위로 섞는 것입니다. 그런 다음 각 항목을 바닥 (가장 작은 양동이)에서 시작하여 충분한 공간이있을 때까지 위로 이동하는 양동이에 넣으려고합니다.

입력 유형에 따라 정렬 알고리즘은 O (n ^ 2)에서 좋은 결과를 제공 할 수 있습니다. 다음은 정렬 된 출력의 예입니다.

다음은 주문 알고리즘 삽입입니다.

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

GitHub의에 프로젝트 - https://github.com/gradbot/Parabolic-Knapsack

공개 저장소이므로 자유롭게 분기하고 다른 알고리즘을 추가하십시오. 흥미로운 문제이므로 앞으로 더 추가 할 것입니다.

---

단순화

먼저 문제를 단순화하고 싶습니다.

• 축을 전환하고 서로 추가하면 x2 성장이 발생합니다.
• 나는 그것이 닫힌 간격의 포물선이라고 가정 [a, b], where a = 0하고이 예에서는b = 3

b(간격의 두 번째 부분)과 w(세그먼트의 너비 ) 가 주어지면 총 세그먼트 수를 n=Floor[b/w]. 이 경우 Riemann 합계를 최대화하는 사소한 경우가 있으며 i 번째 세그먼트 높이를 얻는 함수는 다음과 같습니다 f(b-(b*i)/(n+1))). 사실 그것은 가정이며 100 % 확신하지는 않습니다.

함수 실수 값에 대한 17닫힌 간격의 세그먼트에 대한 최대 예 :[0, 3]Sqrt[x]

이 경우 세그먼트 높이 함수는 Re[Sqrt[3-3*Range[1,17]/18]]이고 값은 다음과 같습니다.

• 정확한 형식 :

{Sqrt [17/6], 2 Sqrt [2/3], Sqrt [5/2], Sqrt [7/3], Sqrt [13/6], Sqrt [2], Sqrt [11/6], Sqrt [5/3], Sqrt [3/2], 2 / Sqrt [3], Sqrt [7/6], 1, Sqrt [5/6], Sqrt [2/3], 1 / Sqrt [2], 1 / Sqrt [3], 1 / Sqrt [6]}

• 대략적인 형태 :

{1.6832508230603465, 1.632993161855452, 1.5811388300841898, 1.5275252316519468, 1.4719601443879744, 1.4142135623730951, 1.35400640077266, 1.2909944487358056, 1.224744871391589, 1.1547005383792517, 1.0801234497346435, 1,0.9128709258277267729046311865475258,809273500710, 0.9128709291752735026, 0.896164965258,809276969, 0.896965)

보관 한 것은 부분적으로 채워진 빈이 있는 빈 포장 문제 입니다.

b 찾기

경우 b를 알 수 없거나 우리의 임무는 가능한 가장 작은을 찾을 수 있습니다 b모든 스틱은 초기 무리 맞게 어떤 형태 아래. 그런 다음 최소한 b값을 다음으로 제한 할 수 있습니다 .

1. lower limit : if sum of segment heights = sum of stick heights
2. upper limit : number of segments = number of sticks longest stick < longest segment height

One of the simplest way to find b is to take a pivot at (higher limit-lower limit)/2 find if solution exists. Then it becomes new higher or lower limit and you repeat the process until required precision is met.

---

When you are looking for b you do not need exact result, but suboptimal and it would be much faster if you use efficient algorithm to find relatively close pivot point to actual b.

For example:

• sort the stick by length: largest to smallest
• start 'putting largest items' into first bin thy fit

---

This is equivalent to having multiple knapsacks (assuming these blocks are the same 'height', this means there's one knapsack for each 'line'), and is thus an instance of the bin packing problem.

See http://en.wikipedia.org/wiki/Bin_packing

---

How can I stack these sticks within the parabola such that I am minimizing the (vertical) space it uses as much as possible?

Just deal with it like any other Bin Packing problem. I'd throw meta-heuristics on it (such as tabu search, simulated annealing, ...) since those algorithms aren't problem specific.

For example, if I'd start from my Cloud Balance problem (= a form of Bin Packing) in Drools Planner. If all the sticks have the same height and there's no vertical space between 2 sticks on top of each other, there's not much I'd have to change:

• Rename Computer to ParabolicRow. Remove it's properties (cpu, memory, bandwith). Give it a unique level (where 0 is the lowest row). Create a number of ParabolicRows.
• Rename Process to Stick
• Rename ProcessAssignement to StickAssignment
• Rewrite the hard constraints so it checks if there's enough room for the sum of all Sticks assigned to a ParabolicRow.
• Rewrite the soft constraints to minimize the highest level of all ParabolicRows.

---

I'm very sure it is equivalent to bin-packing:

informal reduction

Be x the width of the widest row, make the bins 2x big and create for every row a placeholder element which is 2x-rowWidth big. So two placeholder elements cannot be packed into one bin.

To reduce bin-packing on parabolic knapsack you just create placeholder elements for all rows that are bigger than the needed binsize with size width-binsize. Furthermore add placeholders for all rows that are smaller than binsize which fill the whole row.

This would obviously mean your problem is NP-hard.

For other ideas look here maybe: http://en.wikipedia.org/wiki/Cutting_stock_problem

---

Most likely this is the 1-0 Knapsack or a bin-packing problem. This is a NP hard problem and most likely this problem I don't understand and I can't explain to you but you can optimize with greedy algorithms. Here is a useful article about it http://www.developerfusion.com/article/5540/bin-packing that I use to make my php class bin-packing at phpclasses.org.

---

Props to those who mentioned the fact that the levels could be at varying heights (ex: assuming the sticks are 1 'thick' level 1 goes from 0.1 unit to 1.1 units, or it could go from 0.2 to 1.2 units instead)

You could of course expand the "multiple bin packing" methodology and test arbitrarily small increments. (Ex: run the multiple binpacking methodology with levels starting at 0.0, 0.1, 0.2, ... 0.9) and then choose the best result, but it seems like you would get stuck calulating for an infinite amount of time unless you had some methodlogy to verify that you had gotten it 'right' (or more precisely, that you had all the 'rows' correct as to what they contained, at which point you could shift them down until they met the edge of the parabola)

Also, the OP did not specify that the sticks had to be laid horizontally - although perhaps the OP implied it with those sweet drawings.

이러한 문제를 최적으로 해결하는 방법을 모르겠지만 스틱을 무작위로 배치 한 다음 포물선 '내부'인지 테스트 할 수있는 특정 경우가있을 것입니다. 행. (1 개의 긴 막대로 채우려는 좁은 포물선의 경우를 고려하십시오.)

나는 그들 모두를 거기에 던져서 흔들어 라 말한다.)

참고 URL : https://stackoverflow.com/questions/5084817/parabolic-knapsack