Problema dello zaino
Lezione 7 di 15 del corso Sfide sulla ricorsione - Padroneggia il pensiero ricorsivo di Coddy.
Sfida
MedioIl problema dello zaino è un problema famoso.
In questo problema, hai uno zaino con una capacità di peso predefinita e degli oggetti, ciascuno dei quali ha un peso e un valore.
Il tuo compito è inserire il maggior valore possibile rispettando il limite di peso dello zaino.
Per esempio,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Peso dello zaino - 10
La soluzione consiste nel prendere gli oggetti con pesi 1 e 8 e valori 20 e 40.
Il valore massimo è 60 e il peso totale è 9 (che è minore o uguale a 10, quindi è un peso valido).
Scrivi una funzione chiamata knapsack che riceva un intero W e due array di interi values e weights e restituisca la soluzione al problema dello zaino usando i valori di input (il valore massimo che lo zaino può contenere).
Provalo tu
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Scrivi il codice qui
return 0;
}
Tutte le lezioni di Sfide sulla ricorsione - Padroneggia il pensiero ricorsivo
2Sfide di livello intermedio
Problema dello zainoNumero di quadratiRisultato intercalatoCombinazioni con sommaTrova una ternaDividi l'arrayEsercitati da solo: Compilatore C online