我正在努力解决这个问题
https://warmup.kattis.com/problems/vegetables
我想知道的是一个人应该如何把一个蔬菜分成两块。
如果我使wleft=wright=1/2*w，则不可能获得与sample相同的输出。
在他们写的提示/提示/见解中
见解：一种蔬菜的所有切块重量都是一样的。
但这对我来说毫无意义。
1000 1400个
会给我
1400至700 700
1000个
没有比率是700/1000，所以我们必须除以1000
1400至700 700
1000->500 500个
现在我不知道该怎么划分，因为在这种情况下我只能做3个。
最佳答案
这可以归结为对削减数量的广度优先搜索，并结合不同的可能削减。首先，使用零截检查解，然后使用一截等检查所有解，直到找到一个大小完全相等的解。
注：
考虑下一次切割时，切最小的蔬菜是没有意义的，因为这只会使比例更糟。
所有蔬菜的任何解决方案也是任何两种蔬菜的解决方案。您可以使用此选项来修剪搜索，以避免在无望的情况下搜索最佳切割。
如果你想象一个图，你有一个根顶点，每个蔬菜都是完整的。然后每条边都切一棵蔬菜，形成一个新顶点。一开始，这看起来像一棵树，但它只是一个达格切割两个蔬菜的顺序无关紧要，切割两个蔬菜后，路径将再次收敛到单个顶点。请确保不要尝试同一个顶点两次，因为它会放大您必须处理的可能切割的数量。
结合以上三个音符，唯一值得考虑的是将最大的蔬菜切成更多的片利用这些知识，您应该能够有效地实现这个算法。
关于algorithm - 煮蔬菜的最低切数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26177052/