Modulo 4 · Astrarre difficile R

Progetti da finanziare

La fondazione di una banca locale ha un bando per progetti sociali sul territorio: doposcuola, assistenza agli anziani, corsi di lingua per stranieri. Ogni progetto arrivato in commissione ha un costo (in migliaia di euro) e una stima delle persone che raggiungerà. Un progetto si finanzia per intero o non si finanzia: non esistono mezzi progetti. La somma dei costi dei progetti scelti deve stare dentro il budget, che può anche avanzare; se i costi arrivano esattamente al budget, la combinazione va bene.

La commissione vuole sapere qual è il numero massimo di persone che si possono raggiungere con il budget disponibile. Scegliere a occhio non funziona: con 100 mila euro e tre progetti da 70, 50 e 40 mila, il più grande (400 persone) lascia fuori gli altri due, mentre 50 + 40 ne raggiungono 490. Se nessun progetto entra nel budget, la risposta è 0.

Scrivi la funzione persone_massime(budget, costi, persone). Lo schema è quello dei due fornitori: una funzione valuta(scelte, budget, costi, persone) che riceve un vettore di TRUE/FALSE, uno per progetto, e restituisce le persone raggiunte (0 se la spesa supera il budget); una funzione ricorsiva migliore(scelte, budget, costi, persone) che aggiunge una scelta alla volta, una volta TRUE e una volta FALSE, con il caso base quando le scelte sono tante quanti i progetti, e tiene il risultato più grande con max(a, b), che restituisce il maggiore fra due numeri; infine persone_massime che chiama migliore partendo da c(), nessuna scelta fatta. Ricorda che costi[scelte] con un vettore logico tiene solo i progetti finanziati.

Input

budget numero — fondi disponibili, in migliaia di euro
costi vettore di numeri — costo di ciascun progetto, in migliaia di euro
persone vettore di numeri — persone raggiunte da ciascun progetto, stesso ordine di costi

Output

raggiunte numero — il numero massimo di persone raggiungibili restando nel budget

da scrivere come funzione persone_massime

Nota

Lab difficile: le regole sono nel testo, gli esempi non ci sono. Scrivi tu la specifica prima del codice.

Ti serve: vettori · indicizzazione · ciclo for · if/else · operatori logici

# ---- Prima funzione: quante persone raggiunge una scelta completa ----
# scelte è un vettore di TRUE/FALSE, uno per progetto

valuta <- function(scelte, budget, costi, persone){
  spesa <- sum(costi[scelte])           # solo i progetti finanziati
  if(spesa <= budget){
    return(sum(persone[scelte]))
  }else{
    return(0)                           # fuori budget: non vale
  }
}

# ---- Seconda funzione: prova tutte le combinazioni ----

migliore <- function(scelte, budget, costi, persone){
  if(length(scelte) == length(costi)){
    return(valuta(scelte, budget, costi, persone))   # caso base: ho deciso tutto
  }

  con_progetto <- migliore(c(scelte, TRUE), budget, costi, persone)     # il prossimo lo finanzio
  senza_progetto <- migliore(c(scelte, FALSE), budget, costi, persone)  # ... oppure no

  return(max(con_progetto, senza_progetto))
}

# ---- La funzione principale: parte da nessuna scelta ----

persone_massime <- function(budget, costi, persone){
  return(migliore(c(), budget, costi, persone))
}

persone_massime(100, c(70, 50, 40), c(400, 260, 230))   # 490

La fondazione di una banca locale ha un bando per progetti sociali sul territorio: doposcuola, assistenza agli anziani, corsi di lingua per stranieri. Ogni progetto arrivato in commissione ha un costo (in migliaia di euro) e una stima delle persone che raggiungerà. Un progetto si finanzia per intero o non si finanzia: non esistono mezzi progetti. La somma dei costi dei progetti scelti deve stare dentro il budget, che può anche avanzare; se i costi arrivano esattamente al budget, la combinazione va bene.

La commissione vuole sapere qual è il numero massimo di persone che si possono raggiungere con il budget disponibile. Scegliere a occhio non funziona: con 100 mila euro e tre progetti da 70, 50 e 40 mila, il più grande (400 persone) lascia fuori gli altri due, mentre 50 + 40 ne raggiungono 490. Se nessun progetto entra nel budget, la risposta è 0.

Scrivi la funzione persone_massime(budget, costi, persone). Lo schema è quello dei due fornitori: una funzione valuta(scelte, budget, costi, persone) che riceve un vettore di TRUE/FALSE, uno per progetto, e restituisce le persone raggiunte (0 se la spesa supera il budget); una funzione ricorsiva migliore(scelte, budget, costi, persone) che aggiunge una scelta alla volta, una volta TRUE e una volta FALSE, con il caso base quando le scelte sono tante quanti i progetti, e tiene il risultato più grande con max(a, b), che restituisce il maggiore fra due numeri; infine persone_massime che chiama migliore partendo da c(), nessuna scelta fatta. Ricorda che costi[scelte] con un vettore logico tiene solo i progetti finanziati.