c# - 动态规划 - 移动

Question

我必须在这个问题上应用动态规划，但我不太确定如何。

手机上有50个按钮，2000个字母(按字母排序)。每个字母在按钮上都有 k 位置(字母按 k 键输入)。然后我们知道，这封信用了多少。程序将确定字母应该放在哪个按钮上，以便找出最少按下次数。

输入:

按钮数量

字母数

平均字母中每个字符的出现频率。示例:

3 // number of buttons

5 // number of letters

1 // frequency of first letter

1 // frequency of second letter

1 // frequency of third letter

1 // frequency of fourth letter

1 // frequency of fifth letter

解决方法:

按钮:1 2 | 3 4 | 5

1 * 1 + 2 * 1 = 3

1 * 1 + 2 * 1 = 3

1 * 1 = 1输出为:3 + 3 + 1 = 7

程序将输出:7

我已经解决了这个例子。我创建了两个矩阵。一个有 SS 维度，另一个有 KS 维度。 SS矩阵中每个元素代表按钮的价格，有从i坐标到j坐标的字符。在 KS 矩阵中，i 表示按钮的数量，j 表示给 j 的字符。

我有一个问题，如何找到成本最低的按钮。

例如:

我想在 [2,3] 坐标中的 KS 表中找到值。这意味着，我们将三个字符拆分为两个按钮。最佳解决方案是，一个按钮将有 2 个字符，另一个按钮将有一个字符。在 SS 中，解决方案是 [1,1] + [2,3] 或 [1,2] + [3,3]。

我会感激每一个建议。

表 S*S

1 3 6 10 15

0 1 3 6 10

0 0 1 3 6

0 0 0 1 3

0 0 0 0 1

表 K*S

1 3 6 10 15

0 2 4 6 9

0 0 3 5 7

Answer 1

您可能熟悉霍夫曼编码背后的推理，其中为了获得最佳使用或最高效率，应该以最少的工作量获得最高频率的字母。这个逻辑也适用于你的问题。您希望执行最少的按钮按下次数以达到最高频率的字母。

假设我们有 numB 个按钮 和 numL 个字母。我们还假设我们有一个名为 Letter 的对象，它具有 char letter 和 int frequency 属性，最后，我们有 LetterCol，它是字母对象。 (我的 C# 生锈了，请耐心等待)。

第一步:
按频率对这些字母进行排序。(任何排序功能都可以)。我们将使用一组字母 Keypad 的数组列表。它的功能就像一张 map 。

Keypad 中的每个位置都是一个数组列表。每个位置将与一个按钮相关。 Keypad[0] 与 button 0 相关。 Keypad[0] 也是一个字母 ArrayList。这将填充我们希望放在 button 0 上的字母。

List<ArrayList<Letter>> Keypad = new ArrayList<>();

第 2 步:
由于 LetterCol 按频率排序，我们只需将每个字母按顺序放在 Keypad 上。我们将使用 mod 函数 % 来确保我们保持在我们的范围内(即，我们不超过按钮的数量 numB)。

for(int i = 0; i < numL; i++)
   Keypad[i%numB].add(LetterCol[i]);

现在，我们的安置过程已经完成。每个字母都放在它的最佳位置。现在是计算输出的时候了。

第 3 步:
我们现在需要访问 Keypad 中的每个位置并检索这些 ArrayList 中的每个字母。

int output = 0;
for(int i = 0; i < numB; i++)
   for(int j = 0; j < Keypad[i].count; j++){
      output += (j+1)*(Keypad[i][j].frequency);

//我的语法可能不正确，在Java中是:output += (j+1)*(Keypad[i].get[j].frequency);

现在我们包含了最优的输出。在您的数字示例中，您转到每个按钮并将按下的次数乘以字母的频率。这些 for 循环执行相同的计算。我们转到每个按钮 i，将按下的次数 j+1 乘以字母 Keypad[i][j].frequency 的频率>.