Bài toán cái túi
Bài học 7 trên 15 trong khóa học Thử thách đệ quy: làm chủ tư duy đệ quy của Coddy.
Thử thách
Trung bìnhBài toán ba lô là một bài toán nổi tiếng.
Trong bài toán này, bạn có một chiếc ba lô có giới hạn trọng lượng định trước và các món đồ, mỗi món có trọng lượng và giá trị riêng.
Nhiệm vụ của bạn là mang theo tổng giá trị lớn nhất mà không vượt quá giới hạn trọng lượng của ba lô.
Ví dụ:
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Trọng lượng của ba lô - 10
Lời giải là chọn các món đồ có trọng lượng 1 và 8, với giá trị lần lượt là 20 và 40.
Giá trị lớn nhất là 60 và tổng trọng lượng là 9 (nhỏ hơn hoặc bằng 10, nghĩa là trọng lượng hợp lệ).
Viết một hàm có tên knapsack nhận vào một số nguyên W cùng hai mảng số nguyên values và weights, rồi trả về lời giải cho bài toán ba lô dựa trên các giá trị đầu vào (giá trị lớn nhất mà ba lô có thể mang).
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Viết code tại đây
return 0;
}
Tất cả bài học trong Thử thách đệ quy: làm chủ tư duy đệ quy
Tự luyện tập: Trình biên dịch C online