提问者:小点点

制造两个重量至少为k的袋子所需的最少元素数?


假设给你一个数字k和一个具有一定权重的对象数组。现在你的任务是找到两个袋子里能放的物体的最小数量,使每个袋子至少重K.br>你只能把这些物体当作一个整体,不允许破碎。另外,如果一个物品放在一个袋子里,它就不能放在另一个袋子里。br>

这个问题在我看来很简单。当你只需要装满一个袋子时,我也做过类似的问题。我使用的想法是,你访问每一个对象,问自己如果我把它放在袋子里怎么办,如果我不把它放在袋子里怎么办?您递归地执行此操作,直到达到您期望的权重或者您没有更多的对象。调用递归函数时取最小值。br>

但是,我不能够理解如何跟踪在包1中用完的所有对象,以便我不包括在包2.br>

少量测试用例br>

    对象数(N)=1
    [10br>输出:-1(不可能)/li> 对象数(N)=3
    [2,2,2br>输出:2/li>

共1个答案

匿名用户

我将专注于你指出的作为你实际的核心问题,如何保持跟踪你在一个包,另一个包或根本不使用的对象。

列出一个列表(数组,矢量,…任何你喜欢的容器),并记下每个你用过它的对象--或者没有用过它。