109 lines
3.6 KiB
Zig
109 lines
3.6 KiB
Zig
const std = @import("std");
|
|
|
|
const Item = struct {
|
|
name: []const u8,
|
|
weight: usize,
|
|
value: usize,
|
|
};
|
|
|
|
fn knapsack01_dyn(allocator: std.mem.Allocator, items: []const Item, max_weight: usize) !std.ArrayList(*const Item) {
|
|
// Create 2D array for dynamic programming
|
|
var best_value = try allocator.alloc([]usize, items.len + 1);
|
|
defer allocator.free(best_value);
|
|
|
|
for (best_value) |*row| {
|
|
row.* = try allocator.alloc(usize, max_weight + 1);
|
|
}
|
|
defer {
|
|
for (best_value) |row| {
|
|
allocator.free(row);
|
|
}
|
|
}
|
|
|
|
// Initialize with zeros
|
|
for (best_value) |row| {
|
|
@memset(row, 0);
|
|
}
|
|
|
|
// Fill the table
|
|
for (items, 0..) |it, i| {
|
|
for (1..max_weight + 1) |w| {
|
|
if (it.weight > w) {
|
|
best_value[i + 1][w] = best_value[i][w];
|
|
} else {
|
|
best_value[i + 1][w] = @max(
|
|
best_value[i][w],
|
|
best_value[i][w - it.weight] + it.value
|
|
);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Backtrack to find selected items
|
|
var result = std.ArrayList(*const Item).init(allocator);
|
|
var left_weight = max_weight;
|
|
|
|
var i: usize = items.len;
|
|
while (i > 0) : (i -= 1) {
|
|
if (best_value[i][left_weight] != best_value[i - 1][left_weight]) {
|
|
try result.append(&items[i - 1]);
|
|
left_weight -= items[i - 1].weight;
|
|
}
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
pub fn main() !void {
|
|
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
|
|
defer _ = gpa.deinit();
|
|
const allocator = gpa.allocator();
|
|
|
|
const MAX_WEIGHT: usize = 400;
|
|
|
|
const ITEMS = [_]Item{
|
|
.{ .name = "map", .weight = 9, .value = 150 },
|
|
.{ .name = "compass", .weight = 13, .value = 35 },
|
|
.{ .name = "water", .weight = 153, .value = 200 },
|
|
.{ .name = "sandwich", .weight = 50, .value = 160 },
|
|
.{ .name = "glucose", .weight = 15, .value = 60 },
|
|
.{ .name = "tin", .weight = 68, .value = 45 },
|
|
.{ .name = "banana", .weight = 27, .value = 60 },
|
|
.{ .name = "apple", .weight = 39, .value = 40 },
|
|
.{ .name = "cheese", .weight = 23, .value = 30 },
|
|
.{ .name = "beer", .weight = 52, .value = 10 },
|
|
.{ .name = "suntancream", .weight = 11, .value = 70 },
|
|
.{ .name = "camera", .weight = 32, .value = 30 },
|
|
.{ .name = "T-shirt", .weight = 24, .value = 15 },
|
|
.{ .name = "trousers", .weight = 48, .value = 10 },
|
|
.{ .name = "umbrella", .weight = 73, .value = 40 },
|
|
.{ .name = "waterproof trousers", .weight = 42, .value = 70 },
|
|
.{ .name = "waterproof overclothes", .weight = 43, .value = 75 },
|
|
.{ .name = "note-case", .weight = 22, .value = 80 },
|
|
.{ .name = "sunglasses", .weight = 7, .value = 20 },
|
|
.{ .name = "towel", .weight = 18, .value = 12 },
|
|
.{ .name = "socks", .weight = 4, .value = 50 },
|
|
.{ .name = "book", .weight = 30, .value = 10 },
|
|
};
|
|
|
|
var items = try knapsack01_dyn(allocator, &ITEMS, MAX_WEIGHT);
|
|
defer items.deinit();
|
|
|
|
// Print in reverse order (to match original)
|
|
const stdout = std.io.getStdOut().writer();
|
|
var i: usize = items.items.len;
|
|
while (i > 0) : (i -= 1) {
|
|
try stdout.print("{s}\n", .{items.items[i - 1].name});
|
|
}
|
|
|
|
// Calculate totals
|
|
var total_weight: usize = 0;
|
|
var total_value: usize = 0;
|
|
for (items.items) |item| {
|
|
total_weight += item.weight;
|
|
total_value += item.value;
|
|
}
|
|
|
|
try stdout.print("Total weight: {}\n", .{total_weight});
|
|
try stdout.print("Total value: {}\n", .{total_value});
|
|
}
|