这应该由 DP 解决吗？
Should this be solved by DP instead?
我正在尝试解决一个问题：
Given an NxM matrix, each element represents the cost associated to buy an item. Given that we plan to buy M-1 items from each of the N rows, what is the minimum amount that we would have to spend, if we plan to buy items of all M types?
For e.g., if the input is:
2 3 5
3 2 5
4 4 7
the output should be: (2+3) + (2+5) + (4+4) = .
我很困惑这是DP还是贪心
我觉得很贪心，因为我们要买M-1件东西。因此，对于上面示例中的三个 列 中的每一个，我们可以 select 最低值（2、2 和 5) 并将其用于计算最终结果。我又考虑了几个例子，这个逻辑似乎可行，但我不觉得 'confident' 。我无法 'prove' 它。有人可以确认我是否在正确的轨道上吗？
这个问题有一个贪婪的解决方案，这与您 select 计算每一行的最低值的想法密切相关。贪婪的部分不是 select 您要购买的商品，而是选择您不打算购买的商品（每行一个）。
Select每行要丢弃的最大元素。有两种情况：
- 每个 selected 元素属于同一列：搜索每行的第二个最小元素，然后 select 最小化的元素：（行的最大元素 - 行的第二大元素） .
- 至少有两个元素来自不同的列：这些元素是您不打算购买的。
第二种情况很容易看出是真的。在第一种情况下，由于问题限制，至少有一个 selected 元素与另一个 selected 元素不共享同一列。然后，您需要选择其中一个元素替换为同一行中的另一个元素，如果您要这样做 select 接近该最大值的元素以减少支付的增量。
该分析涵盖了所有极端情况，但显然没有得到正式证明。为此，需要进行涉及最佳解决方案转换的分析（当您分开案例时，会更直接或更不直接）。
我正在尝试解决一个问题：
Given an
NxMmatrix, each element represents the cost associated to buy an item. Given that we plan to buyM-1items from each of theNrows, what is the minimum amount that we would have to spend, if we plan to buy items of allMtypes?
For e.g., if the input is:
2 3 5
3 2 5
4 4 7
the output should be: (2+3) + (2+5) + (4+4) = .
我很困惑这是DP还是贪心
我觉得很贪心，因为我们要买M-1件东西。因此，对于上面示例中的三个 列 中的每一个，我们可以 select 最低值（2、2 和 5) 并将其用于计算最终结果。我又考虑了几个例子，这个逻辑似乎可行，但我不觉得 'confident' 。我无法 'prove' 它。有人可以确认我是否在正确的轨道上吗？
这个问题有一个贪婪的解决方案，这与您 select 计算每一行的最低值的想法密切相关。贪婪的部分不是 select 您要购买的商品，而是选择您不打算购买的商品（每行一个）。
Select每行要丢弃的最大元素。有两种情况：
- 每个 selected 元素属于同一列：搜索每行的第二个最小元素，然后 select 最小化的元素：（行的最大元素 - 行的第二大元素） .
- 至少有两个元素来自不同的列：这些元素是您不打算购买的。
第二种情况很容易看出是真的。在第一种情况下，由于问题限制，至少有一个 selected 元素与另一个 selected 元素不共享同一列。然后，您需要选择其中一个元素替换为同一行中的另一个元素，如果您要这样做 select 接近该最大值的元素以减少支付的增量。
该分析涵盖了所有极端情况，但显然没有得到正式证明。为此，需要进行涉及最佳解决方案转换的分析（当您分开案例时，会更直接或更不直接）。