Mam problem z moją pracą domową.
Biorąc pod uwagę tablicę wymiarów m x n jest podany, pokrój tę płytę na prostokątne kawałki o najlepszej całkowitej cenie. Matryca podaje cenę za każdy możliwy rozmiar planszy przez oryginalną, nieprzyciętą planszę.
Rozważmy 2 x 2 plansza z matrycą cenową:
3 4
3 6
Na przykład mamy stały koszt dla każdego cięcia 1.
Kawałek długości 1 x 1 jest warte 3.
Poziomy kawałek długości 1 x 2 jest warte 4.
Pionowy kawałek długości 1 x 2 jest warte 3.
Cała deska jest warta 6.
W tym przykładzie optymalny zysk to 9, ponieważ tniemy deskę 1 x 1 kawałki. Każda sztuka jest warta 3 i zrobiliśmy 3 wyciąć, tak 4 x 3 - 3 x 1 = 9.
Drugi przykład:
1 2
3 4
Teraz muszę rozważyć wszystkie rozwiązania:
41x1kawałki są warte4x1 - (cost of cutting) 3x1 = 12poziomy1x2 is worth 2x2 - (cost of cutting) 1x1 = 32pionowy1x2 is worth 3x2 - (cost of cutting) 1x1 = 5-> najlepszy optymalny zysk1poziomy1x2 + 2 x (1x1) pieces is worth 2 + 2 - (cost of cutting) 2 = 21pionowy1x2 + 2 x (1x1) pieces is worth 3 + 2 - (cost of cutting) 2 = 3
Przeczytałem dużo o algorytmie cięcia prętów, ale nie mam pojęcia, jak ugryźć ten problem. Czy masz jakies pomysły?
Odpowiedzi:
2 dla odpowiedzi № 1Zrobiłem to w Pythonie. Algorytm jest
best_val= wartość bieżącej płyty- sprawdź każde poziome i pionowe cięcie, aby uzyskać lepszą wartość
- dla punktu cięcia <= połowa bieżącego wymiaru (jeśli brak, zwróć wartość początkową)
- powtarzaj na dwóch uformowanych deskach
- jeśli suma wartości>
best_val - ...
best_val= ta suma - ... zapisz punkt i kierunek cięcia
- zwracany wynik: best_val, punkt cięcia i kierunek
„Nie jestem pewien, co będziesz chciał zwracać wartości; Oddałem najlepszą wartość i drzewo desek. Dla twojego drugiego przykładu jest to
(5, [[2, 1], [2, 1]])
Kod z debugowaniem śladów (indent i oznaczone prints):
indent = ""
indent_len = 3
value = [[1, 2],
[3, 4]
]
def best_cut(high, wide):
global indent
print indent, "ENTER", high, wide
indent += " " * indent_len
best_val = value[high-1][wide-1]
print indent, "Default", best_val
cut_vert = None
cut_val = best_val
cut_list = []
# Check horizontal cuts
for h_cut in range(1, 1 + high // 2):
print indent, "H_CUT", h_cut
cut_val1, cut_list1 = best_cut(h_cut, wide)
cut_val2, cut_list2 = best_cut(high - h_cut, wide)
cut_val = cut_val1 + cut_val2
if cut_val > best_val:
cut_list = [cut_list1, cut_list2]
print indent, "NEW H", h_cut, cut_val, cut_list
best_val = cut_val
cut_vert = False
best_h = h_cut
# Check vertical cuts
for v_cut in range(1, 1 + wide // 2):
print indent, "V_CUT", v_cut
cut_val1, cut_list1 = best_cut(high, v_cut)
cut_val2, cut_list2 = best_cut(high, wide - v_cut)
cut_val = cut_val1 + cut_val2
if cut_val > best_val:
cut_list = [cut_list1, cut_list2]
print indent, "NEW V", v_cut, cut_val, cut_list
best_val = cut_val
cut_vert = True
best_v = v_cut
# Return result of best cut
# Remember to subtract the cut cost
if cut_vert is None:
result = best_val , [high, wide]
elif cut_vert:
result = best_val-1, cut_list
else:
result = best_val-1, cut_list
indent = indent[indent_len:]
print indent, "LEAVE", cut_vert, result
return result
print best_cut(2, 2)
Wynik (wielkość zysku i cięcia) dla każdego z dwóch testów:
(9, [[[1, 1], [1, 1]], [[1, 1], [1, 1]]])
(5, [[2, 1], [2, 1]])
1 dla odpowiedzi nr 2
Pozwolić f(h,w) reprezentują najlepszą całkowitą cenę możliwą do uzyskania dla deski o wysokości h i szerokość w z ceną cięcia c. Następnie
f(h,w) = max(
price_matrix(h, w),
f(i, w) + f(h - i, w) - c,
f(h, j) + f(h, w - j) - c
)
for i = 1 to floor(h / 2)
for j = 1 to floor(w / 2)
Oto przykład w JavaScript, który zwraca wypełnioną tabelę podaną w macierzy cen. Odpowiedź znajduje się w prawym dolnym rogu.
function f(prices, cost){
var m = new Array(prices.length);
for (let i=0; i<prices.length; i++)
m[i] = [];
for (let h=0; h<prices.length; h++){
for (let w=0; w<prices[0].length; w++){
m[h][w] = prices[h][w];
if (h == 0 && w == 0)
continue;
for (let i=1; i<(h+1>>1)+1; i++)
m[h][w] = Math.max(
m[h][w],
m[i-1][w] + m[h-i][w] - cost
);
for (let i=1; i<(w+1>>1)+1; i++)
m[h][w] = Math.max(
m[h][w],
m[h][i-1] + m[h][w-i] - cost
);
}
}
return m;
}
$("#submit").click(function(){
let prices = JSON.parse($("#input").val());
let result = f(prices, 1);
let str = result.map(line => JSON.stringify(line)).join("<br>");
$("#output").html(str);
});<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<textarea id="input">[[3, 4],
[3, 6]]</textarea>
<p><button type="button" id="submit">Submit</button></p>
<div id="output"><div>0 dla odpowiedzi № 3
Kilka myśli na temat problemu, a nie odpowiedź:
Dawno temu studiowałem programowanie dynamiczne, ale napisałem następujący pseudo kod, który jest uważany za O (n ^ 2):
// "Board"-class not included
val valueOfBoards: HashMap<Board, int>
fun cutBoard(b: Board, value: int) : int {
if (b.isEmpty()) return 0
if (valueOfBoards[b] > value) {
return 0;
} else {
valueOfBoards[b] = value
}
int maxValue = Integer.MIN_VALUE
for (Board piece : b.getPossiblePieces()) {
val (cuttingCost, smallerBoard) = b.cutOffPiece(piece)
val valueGained: int = piece.getPrice() - cuttingCost
maxValue = Max(maxValue, valueGained + cutBoard(smallerBoard, value + valueGained))
}
return maxValue;
}
Klasa tablicy nie jest trywialnie zaimplementowana, oto kilka szczegółów:
// returns all boards which fits in the current board
// for the initial board this will be width*height subboards
board.getPossiblePieces()
// returns a smaller board and the cutting cost of the cut
// I can see this becoming complex, depends on how one chooses to represent the board.
board.cutOffPiece(piece: Board)
W tej chwili nie jest dla mnie jasne, czy cutOffPiece() łamie algorytm, ponieważ nie wiesz, jak optymalnie ciąć. Myślę, że ponieważ algorytm przejdzie od większych kawałków do mniejszych kawałków, w pewnym momencie będzie dobrze.
Próbowałem rozwiązać ponowne obliczanie problemów podrzędnych (identyczne tablice), zapisując wyniki w coś takiego HashMap<Board, price> i porównanie nowej planszy z najlepszą przechowywaną ceną przed kontynuowaniem.
0 dla odpowiedzi nr 4
Zgodnie z twoimi odpowiedziami przygotowałem implementację „od dołu do góry” i „odgórnie”.
Od dołu:
function bottomUp($high, $wide, $matrix){
$m = [];
for($h = 0; $h < $high; $h++){
for($w = 0; $w < $wide; $w++){
$m[$h][$w] = $matrix[$h][$w];
if($h == 0 && $w == 0){
continue;
}
for($i = 1; $i < ($h + 1 >> 1) + 1; $i++){
$m[$h][$w] = max(
$m[$h][$w],
$m[$i - 1][$w] + $m[$h - $i][$w] - CUT_COST
);
}
for($i = 1; $i < ($w + 1 >> 1) + 1; $i++){
$m[$h][$w] = max(
$m[$h][$w],
$m[$h][$i - 1] + $m[$h][$w - $i] - CUT_COST
);
}
}
}
return $m[$high-1][$wide-1];
}
Do góry:
function getBestCut($high, $wide, $matrix){
global $checked;
if(isset($checked[$high][$wide])){
return $checked[$high][$wide];
}
$bestVal = $matrix[$high-1][$wide-1];
$cutVert = CUT_VERT_NONE;
$cutVal = $bestVal;
$cutList = [];
for($hCut = 1; $hCut < 1 + floor($high/2); $hCut++){
$result1 = getBestCut($hCut, $wide, $matrix);
$cutVal1 = $result1[0];
$cutList1 = $result1[1];
$result2 = getBestCut($high - $hCut, $wide, $matrix);
$cutVal2 = $result2[0];
$cutList2 = $result2[1];
$cutVal = $cutVal1 + $cutVal2;
if($cutVal > $bestVal){
$cutList = [$cutList1, $cutList2];
$bestVal = $cutVal;
$cutVert = CUT_VERT_FALSE;
$bestH = $hCut;
}
$checked[$hCut][$wide] = $result1;
$checked[$high - $hCut][$wide] = $result2;
}
for($vCut = 1; $vCut < 1 + floor($wide/2); $vCut++){
$result1 = getBestCut($hCut, $vCut, $matrix);
$cutVal1 = $result1[0];
$cutList1 = $result1[1];
$result2 = getBestCut($high, $wide - $vCut, $matrix);
$cutVal2 = $result2[0];
$cutList2 = $result2[1];
$cutVal = $cutVal1 + $cutVal2;
if($cutVal > $bestVal){
$cutList = [$cutList1, $cutList2];
$bestVal = $cutVal;
$cutVert = CUT_VERT_TRUE;
$bestH = $vCut;
}
$checked[$hCut][$vCut] = $result1;
$checked[$high][$wide - $vCut] = $result2;
}
if($cutVert == CUT_VERT_NONE){
$result = [$bestVal, [$high, $wide]];
}else if($cutVert == CUT_VERT_TRUE){
$result = [$bestVal - CUT_COST, $cutList];
}else{
$result = [$bestVal - CUT_COST, $cutList];
}
return $result;
}
Proszę mi powiedzieć, czy są poprawne wdrożenie tej metody?
Zastanawiam się, czy złożoność czasu jest O(m^2*n^2) w metodzie odgórnej?