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

Question

Suppose you are given a number k and an array of objects having some weight. Now your task is to find the minimum number of objects that you can put in two bags such that each bag weigh at least k.
You can only take the objects as whole no breaking is allowed. Also, if an object is put in one bag it cannot be put into the other bag.

这个问题对我来说似乎很简单。当您只需要装满一个袋子时，我也遇到过类似的问题。我使用的想法是你访问每个对象问问自己如果我把它放在包里会怎样，如果我不放在包里会怎样？你递归地这样做，直到达到你想要的重量或者你没有更多的物体。调用递归函数时取最小值。

但是，我无法理解如何跟踪包 1 中用完的所有物品，以便不将其包含在包 2 中。

几个测试用例

期望权重 (k) = 4
对象数 (N) = 1
[10]
输出：-1（不可能）
期望体重 (k) = 2
对象数 (N) = 3
[2,2,2]
输出：2

Answer 1

我将重点关注您指出的实际核心问题，即如何跟踪您在一个袋子、另一个袋子或根本不使用的物品。

制作一个列表（数组、向量……任何您喜欢的容器）并记下您使用或不使用它的每个对象。

index	value	meaning
0	0	not used
1	0	not used
2	0	not used
3	1	used in one bag
4	2	used in other bag

根据你的问题，我不清楚输入中给定的所有对象的权重是相同还是不同。如果重量不同，那么您很可能已经有了一个容器来跟踪每个物体的重量。修改该容器或使用第二个非常相似的容器将帮助您存储“使用位置”信息。

由于
，我有意不进行详细介绍 How do I ask and answer homework questions?

Answer 2

我不知道这是否回答了你的问题，但仍然...... 你可以做一件事：最初创建两个空数组，比如 Bag_1 和 Bag_2。当你一个一个地递归遍历所有元素时，将该元素从数组中弹出并将其附加到 Bag_1 或 Bag_2 中，以最佳解决方案为准。如果要多次执行该过程，那么创建原始数组的副本可能会有所帮助，前提是数组的长度合理。

Answer 3

这里是没有动态规划的程序的伪代码。

 sort(a, a+n); // Sort the array of objects having weight
            int sum = a[n-1], count = -1; //Initialise sum and count
            unordered_set<int>log; // Create an unordered set to store logs (Unordered set will not add repetitive values in the log thus decreasing time complexity)
            log.insert(a[n-1]); // insert last element int log initially
            for(int i = n-2; i >=0; i--) {
                sum += a[i]; //increment the sum
                unordered_set<int>temp; //Create a temporary log that will be mapped to main log at the end.
                temp.insert(a[i]); //insert the sum to temp log
                for (auto it = log.begin(); it != log.end(); ++it) { //loop over all logs seen till now
                    temp.insert(*it + a[i]); // Add current sum to each of them and insert it to temp log thus creating all possible combinations.
                    if((a[i] + *it >= k) && (sum - a[i] - *it >= k)) { //Condition to check if bags have been filled with at least k weight.
                        count = n-i; // update the current count. This will be the ans.
                        break;
                    }
                    if(a[i] >= k && sum - a[i] >= k) {
                        count = n-i;
                        break;
                    }
                }
    
                if(count != -1) { //Condition to check if it's not possible to make such a combination.
                    break;
                }
                log.insert(temp.begin(), temp.end()); // add all temp to main log.
            }
            cout << count << endl; //print ans.

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

Minimum number of elements required to make two bags of at least k weight?

c++

recursion

dynamic-programming