Guide Programmation dynamique · 3/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
This chapter implements 0/1 knapsack in Python (full table with reconstruction, then a single row), adds an LCS function that returns the subsequence, and ports the one-row knapsack to C++, Java and TypeScript.
You have n items, each with a weight and a value, and a bag that holds at most capacity weight. Each item is either taken once or left behind ("0/1"). Maximize the total value.
best[i][c] = the highest value using only the first i items with capacity c.i (best[i-1][c]), or take it if it fits (best[i-1][c - w] + v); keep the larger.best[0][c] = 0, since no items means no value.def knapsack(weights: list[int], values: list[int], capacity: int) -> tuple[int, list[int]]:
n = len(weights)
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c]
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v
chosen, c = [], capacity
for i in range(n, 0, -1):
if best[i][c] != best[i - 1][c]:
chosen.append(i - 1)
c -= weights[i - 1]
return best[n][capacity], chosen[::-1]
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) # (9, [1, 2])Line by line:
best has n + 1 rows and capacity + 1 columns; row 0 stays all zeros as the base case.i describes item i - 1, because Python lists are zero-based.best[i][c] = best[i - 1][c] is the "skip" choice, which is always allowed.if tries the "take" choice: only when the item fits, and only kept when it is strictly better.i - 1 and row i at the current capacity, item i - 1 must have been taken, so we record it and subtract its weight.In the example the best choice is items 1 and 2 (weight 3 + 4, value 4 + 5 = 9).
Row i only reads row i - 1, so a single list can hold both if we update it carefully. Iterating capacities from high to low guarantees that best[c - w] still holds the previous row's value when it is read; that is what keeps each item to at most one use.
def knapsack_value(weights: list[int], values: list[int], capacity: int) -> int:
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # high to low: each item at most once
best[c] = max(best[c], best[c - w] + v)
return best[capacity]
print(knapsack_value([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9Iterating from low to high instead lets an item be reused within the row, which solves the unbounded knapsack. One loop direction is the whole difference.
def lcs(a: str, b: str) -> str:
n, m = len(a), len(b)
L = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
if a[i] == b[j]:
L[i][j] = L[i + 1][j + 1] + 1
else:
L[i][j] = max(L[i + 1][j], L[i][j + 1])
out, i, j = [], 0, 0
while i < n and j < m:
if a[i] == b[j]:
out.append(a[i])
i, j = i + 1, j + 1
elif L[i + 1][j] >= L[i][j + 1]:
i += 1
else:
j += 1
return "".join(out)
print(lcs("ABCBDAB", "BDCABA")) # BDABHere L[i][j] describes the suffixes a[i:] and b[j:], so the table is filled backwards and reconstruction walks forwards from (0, 0) with no final reversal.
#include <algorithm>
#include <iostream>
#include <vector>
long long knapsack(const std::vector<int>& weights, const std::vector<long long>& values, int capacity) {
std::vector<long long> best(capacity + 1, 0);
for (size_t i = 0; i < weights.size(); ++i) {
for (int c = capacity; c >= weights[i]; --c) {
best[c] = std::max(best[c], best[c - weights[i]] + values[i]);
}
}
return best[capacity];
}
int main() {
std::cout << knapsack({1, 3, 4, 5}, {1, 4, 5, 7}, 7) << '\n'; // 9
}Values use long long because sums of many large values can overflow a 32-bit int.
public final class Knapsack {
static long knapsack(int[] weights, long[] values, int capacity) {
long[] best = new long[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int c = capacity; c >= weights[i]; c--) {
best[c] = Math.max(best[c], best[c - weights[i]] + values[i]);
}
}
return best[capacity];
}
public static void main(String[] args) {
System.out.println(knapsack(new int[] {1, 3, 4, 5}, new long[] {1, 4, 5, 7}, 7)); // 9
}
}function knapsack(weights: number[], values: number[], capacity: number): number {
const best = new Array<number>(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let c = capacity; c >= weights[i]; c--) {
best[c] = Math.max(best[c], best[c - weights[i]] + values[i]);
}
}
return best[capacity];
}
console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9All four versions have the same shape: one array of size capacity + 1, an outer loop over items and an inner loop over capacities from high to low.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.