Masalah Ransel
Pelajaran 7 dari 15 dalam kursus Tantangan Rekursi: Kuasai Cara Berpikir Rekursif di Coddy.
Tantangan
SedangMasalah knapsack adalah masalah yang terkenal.
Dalam masalah ini, kamu memiliki knapsack yang dapat menampung berat tertentu, serta items yang masing-masing memiliki berat dan nilai.
Tugasmu adalah mengambil nilai sebanyak mungkin tanpa melebihi batas berat knapsack.
Sebagai contoh,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Berat knapsack - 10
Solusinya adalah mengambil items dengan berat 1 dan 8 serta nilai 20 dan 40.
Nilai maksimum adalah 60, dan berat totalnya 9 (lebih kecil dari atau sama dengan 10, artinya berat tersebut valid).
Tulis fungsi bernama knapsack yang menerima sebuah bilangan bulat W dan dua array bilangan bulat values dan weights, lalu mengembalikan solusi untuk masalah knapsack menggunakan nilai input (nilai maksimum yang dapat ditampung knapsack).
Coba sendiri
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Tulis kodemu di sini
return 0;
}
Semua pelajaran di Tantangan Rekursi: Kuasai Cara Berpikir Rekursif
2Tantangan Menengah
Masalah RanselJumlah KuadratHasil InterleavingKombinasi JumlahTemukan TripletPisahkan ArrayLatihan sendiri: Compiler C online