knapsack.rs

// Enter your code here. Read input from STDIN. Print output to STDOUT

fn check(n:usize, c: &mut Vec<bool>, v: &Vec<u64>,p : u64) -> Option<usize> {
    if n == c.len() { 
        let (count,sum) = v.iter()
            .enumerate()
            .filter(|(i,_)| c[*i])
            .map(|(_,v)| *v)
            .fold((0,0), |(count,sum),e| (count+1,sum+e)); 
            
        if sum == p {
            Some(count)
        } else {
            None
        }
    } else {
        let r1 = check(n+1,c,v,p);
        c[n]=true;
        let r2 = check(n+1,c,v,p);
        c[n]=false;
        match (r1,r2) {
            (Some(l1),Some(l2)) => if l1 > l2 { Some(l1) } else { Some(l2) },
            (Some(l1),None) => Some(l1),
            (None,Some(l2)) => Some(l2),
            _ => None
        }
    }
}

fn main()  {
    let v = vec![1,1,1,1,1,5,10];
    let p = 20;
    
    let mut v = v.into_iter().filter(|x| x<=&p).collect::<Vec<_>>();
    v.sort();
    
    let mut c = vec![false;v.len()];
    let best = check(0,&mut c,&v,p);
    println!("{:?}",best);
}