describe Array do
  describe "#knapsack" do
    it "works with costs of one" do
      ans = [1,2,3,4,5,6].shuffle.knapsack(3) do |i|
        {1, i}
      end
      ans[1].sort!
      ans.should eq({15, [4,5,6]})
    end

    it "works in the non-greedy case" do
      ans = [{2, 2}, {2, 2}, {3, 3}].shuffle.knapsack(4) do |i|
        i
      end
      ans.should eq({4, [{2,2},{2,2}]})
    end
  end
end