Knapsack Problem
الدرس 7 من 15 في دورة تحديات الاستدعاء الذاتي - أتقن التفكير العودي على Coddy.
التحدي
متوسطتعد مشكلة حقيبة الظهر (knapsack problem) مشكلة مشهورة.
في هذه المشكلة، لديك حقيبة ظهر لها وزن محدد مسبقاً يمكنها استيعابه، و عناصر حيث يكون لكل عنصر وزن وقيمة.
مهمتك هي أخذ أكبر قيمة ممكنة ضمن حدود وزن حقيبة الظهر.
على سبيل المثال،
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
وزن حقيبة الظهر - 10
الحل هو أخذ العناصر ذات الأوزان 1 و 8 والقيم 20 و 40.
القيمة القصوى هي 60، والوزن الإجمالي هو 9 (وهو أصغر من أو يساوي 10 مما يعني أنه وزن صالح).
اكتب دالة باسم knapsack تستقبل عدداً صحيحاً W ومصفوفتين من الأعداد الصحيحة values و weights، وتعيد الحل لمشكلة حقيبة الظهر باستخدام قيم المدخلات (أقصى قيمة يمكن أن تستوعبها حقيبة الظهر).
جرّب بنفسك
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// اكتب الكود هنا
return 0;
}
جميع دروس تحديات الاستدعاء الذاتي - أتقن التفكير العودي
2Medium Challenges
Knapsack ProblemNumber of SquaresInterleaving ResultSum CombinationsFind TripletSplit Array