c++ - 给定一个整数 K 和一个大小为 t x t 的矩阵。构造一个由前 t 个小写英文字母组成的字符串 s，使得 s 的总成本为 K

Question

我正在解决这个 problem中途卡住了，寻求帮助和更好的方法来解决这个问题:

problem:

给定一个整数 K和一个大小为 t x t 的矩阵.我们必须构造一个字符串 s由第一个 t 组成小写英文字母使得总成本为s正是K .保证至少存在一个满足给定条件的字符串。在所有可能的字符串中 s这是字典序最小的。

具体来说，英文字母中第 i^th 个字符后跟第 j^th 个字符的成本等于 cost[i][j] .

例如，拥有'a' followed by 'a'的成本由 cost[0][0] 表示以及拥有'b' followed by 'c' is denoted by cost[1][3].的成本

一个字符串的总成本是s中两个连续字符的总成本。对于矩阵成本是

 [1 2] 

 [3 4],

字符串是“abba”，那么我们有

• 'a' 后跟 'b' 的成本是 cost[0][1]=2.
• 'b' 后跟 'b' 的成本是 `cost 0 =4.
• 'b' 后跟 'a' 的成本是成本 0 =3.

字符串“abba”的总成本是 2+4+3=9。

例子: 例如，考虑 K是3 , t为2，成本矩阵为

[2 1]
[3 4]

有两个字符串，其总成本为 3。这些字符串是:

• “aab”
• “吧”

我们的答案将是“aab”，因为它在字典序上是最小的。

my approach

我试图找到并存储 i, j 的所有这些组合使得它总和为期望值 k 或个体等于 k。 对于上面的例子

v={
   {2,1},
   {3,4}
  }

k = 3

和v[0][0] + v[0][1] = 3 & v[1][0] = 3 .我试图将这些对存储在这样的数组中 std::vector<std::vector<std::pair<int, int>>>.基于它，我将创建所有可能的字符串并将存储在集合中，它会按字典顺序给我字符串。

我坚持写了这么多代码:

#include<iostream>
#include<vector>
int main(){
    using namespace std;
    vector<vector<int>>v={{2,1},{3,4}};
    vector<pair<int,int>>k;
    int size=v.size();
    for(size_t i=0;i<size;i++){
        for(size_t j=0;j<size;j++){
            if(v[i][j]==3){
                k.push_back(make_pair(i,j));
            }     
        }
    }
}

求大神帮忙解决一下，谢谢。我的代码只能找到可以等于所需 K 的单个 [i,j] 对。我不知道要收集多个 [i,j] 对，它们总和为所需值，而且我的方法似乎也很幼稚并基于蛮力。寻找更好的感知来解决问题并在代码中实现它。谢谢。

Answer 1

这是一个回溯问题。一般做法是:

a) 从“最小”字母开始，例如'a' 然后递归所有可用的字母。如果你找到一个总和为 K 的字符串，那么你就有了答案，因为这将是字典序上最小的，因为我们是从最小到最大的字母找到它的。

b) 如果在 'a' 中没有找到，则转到下一个字母。

递归/回溯可以这样完成:

• 以字母和K的原值开头
• 探索每个 j = 0 到 t 并将 K 减少成本 [i][j]
• 如果 K == 0 你找到了你的字符串。
• 如果 K < 0 则该路径不可行，因此删除字符串中的最后一个字母，尝试其他路径。

伪代码:

string find_smallest() {
  for (int i = 0; i < t; i++) {
     s = (char)(i+97)
     bool value = recurse(i,t,K,s)
     if ( value ) return s;
     s = ""
  }
  return ""
}

bool recurse(int i, int t, int K, string s) {
   if ( K < 0 ) {
      return false;
   }
   if ( K == 0 ) {
      return true;
   }
   for ( int j = 0; j < t; j++ ) {
      s += (char)(j+97);
      bool v = recurse(j, t, K-cost[i][j], s);
      if ( v ) return true;
      s -= (char)(j+97);
   }
   return false;
}