# Solving the knapsack problem with user provided input

This question was given in my college assignment to be done in C. After doing that, I rewrote the program again in rust. I come from a C/Python background and this is my first rust program. Please critique it. The Program is given inputs in the following format

{num_items} {max_weight}
{item_weight_1} ... {item_weight_num_items}


The output is the number of items and the indices of the chosen items to be put in the bag

use std::io::{self, BufRead};

fn main() {
.lock()
.lines()
.next()
.unwrap()
.unwrap()
.trim()
.split(' ')
.map(|s| s.parse().unwrap())
.collect();
let num_items: i32 = top_line[0];
let max_weight: i32 = top_line[1];
.lock()
.lines()
.next()
.unwrap()
.unwrap()
.trim()
.split(' ')
.map(|s| s.parse().unwrap())
.collect();
let s: (i32, i32) = (1..1 << num_items)
.map(|i| {
(
items
.iter()
.enumerate()
.filter(|&(t, _)| (i >> t & 1 == 1))
.map(|(_, elem)| elem.clone())
.sum::<i32>(),
i,
)
})
.map(|(elem, i)| (max_weight - elem, i))
.filter(|&(elem, _)| (elem >= 0))
.min_by(|(a, _), (b, _)| a.cmp(&b))
.unwrap();
let ans: Vec<i32> = (0..num_items)
.filter(|&t| (s.1 >> t & 1 == 1))
.map(|t| t + 1)
.collect();
println!("{}", ans.len());
println!(
"{}",
ans.iter()
.fold(String::new(), |acc, &arg| acc + &arg.to_string() + " ")
);
}


Example input

6 44
14 13 21 8 56 3


Example output

3
1 4 3


## General

1. You don't have any comments. I recommend you document what basic blocks of code are doing
2. I recommend factoring out the parsing and algorithm parts of your code into different functions.
3. Why prompt the user for the number of input items? You can trivially detect it from the second line input, unless this specifies a different value.
4. Non-descriptive variable names: What does s contain? What does ans mean?
5. The itertools crate is super helpful whenever iterators are involved

## Input Capture / Parsing

1. Read in both lines at once: let lines = io::stdin().lock().lines().take(2);
2. Map over those lines, parsing the integers:
let mut numbers = lines.map(|line| {
line
.trim()
.split(' ')
.map(|s| s.parse::<i32>().unwrap())
});

1. Split the first line:
let first_line = numbers.next().unwrap().take(2).collect::<Vec<_>>();
assert_eq!(first_line.len(), 2);

let num_items = first_line[0];
let max_weights = first_line[1];

1. And grab the items from the second line: let items = numbers.next().unwrap().collect::<Vec<_>>();

## Algorithm Part 1 (s)

1. I'd specify the range as 1..(1 << num_items) to really make clear that second 1 is being shifted, not the whole range.
2. Personally, I prefer my tuples to be easily spotted. I'd set the iteration result a variable then use that in the tuple:
.map(|i| {
let sum = items
.iter()
.enumerate()
.filter(|&(t, _)| (i >> t & 1 == 1))
.map(|(_, elem)| elem.clone())
.sum::<i32>();
(sum, i)
})

1. It's unclear what .filter(|&(t, _)| (i >> t & 1 == 1)) is doing here, but usually bitwise comparisons can be expressed more clearly with other operations.
2. Additionally, i and t should probably be renamed to be more clear.
3. Also, those extra parenthesis around the closure return value should instead be used to group whichever operation takes precedence for clarity of the expression
4. .map(|(_, elem)| elem.clone()) I think can be replaced with .map(|(_, &elem)| elem)
5. Recommend returning (i, sum) instead of (sum, i) to better match the pattern of enumerate
6. Extra parenthesis around the return value in .filter(|&(elem, _)| (elem >= 0))
7. I think .min_by(|(a, _), (b, _)| a.cmp(&b)) can be replaced with .min_by_key(|(x, _)| x)
8. Doesn't look like you ever use s.0 so you can ignore it with let (_, s): (i32, i32) = ...
9. In fact, it doesn't look like you use the i index at all after the first .map(|i| { so you don't need to pass it through the rest of the chain.

## Algorithm Part 2 (ans)

1. You repeat (x >> t & 1 == 1) twice: here and above. Perhaps move it to a clearly-named function?
2. I'd store the ans.iter().fold(...) in a variable before printing the result. Makes the eventual format string output easier to predict.
3. Suggest using format! in the fold:
.fold(|out, &num| format!("{}{} ", out, num))

1. Alternatively, you could use join instead of the fold:
ans.into_iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" ")