1. Where you bin? Bin packing is an optimization problem that models the situation of someone packing items into bins, with the goal of minimizing the number of bins used. Formally, a binpack instance is a set of lengths \((a_{1},\dots,a_{n})\) and a capacity \(C\), and a solution is a set of bins \(\{B_{1},\dots,B_{j}\}\) where each \(B_{i}\subseteq[n]\), \(B_{i}\cap B_{j}=\emptyset\) and \(\bigcup_{i}B_{i}=[n]\), such that for all \(j\), \(\sum_{i\in B_{j}}a_{i}\leq C\).
The binpack decision problem is: given a binpack instance and a number \(k\), is there a solution using \(k\) or fewer bins? Prove, for fun, that the decision version is NP-complete.