给定一个整数 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' 的成本是`cost0=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

在您的实施中，您可能需要另一个成对向量的向量来探索所有候选对象。还有另一个向量，用于更新每个候选人的当前成本。按照这种方法，事情开始变得有点混乱（IMO）。

一个更简洁易懂的选择（又是 IMO）可能是用递归来解决问题：

#include <iostream>
#include <vector>
#define K 3

using namespace std;

string exploreCandidate(int currentCost, string currentString, vector<vector<int>> &v)
{
    if (currentCost == K)
        return currentString;

    int size = v.size();
    int lastChar = (int)currentString.back() - 97;  // get ASCII code
    for (size_t j = 0; j < size; j++)
    {
        int nextTotalCost = currentCost + v[lastChar][j];
        if (nextTotalCost > K)
            continue;

        string nextString = currentString + (char)(97 + j); // get ASCII char
        string exploredString = exploreCandidate(nextTotalCost, nextString, v);
        if (exploredString != "00") // It is a valid path
            return exploredString;
    }

    return "00";
}

int main()
{
    vector<vector<int>> v = {{2, 1}, {3, 4}};

    int size = v.size();
    string initialString = "00"; // reserve first two positions
    for (size_t i = 0; i < size; i++)
    {
        for (size_t j = 0; j < size; j++)
        {
            initialString[0] = (char)(97 + i);
            initialString[1] = (char)(97 + j);
            string exploredString = exploreCandidate(v[i][j], initialString, v);
            if (exploredString != "00") { // It is a valid path
                cout << exploredString << endl;
                return 0;
            }
        }
    }
}

让我们从主要功能开始：
我们定义我们的矩阵并迭代它。对于每个位置，我们定义相应的序列。请注意，我们可以使用索引来获取英文字母表的相应字符，知道在 ASCII 代码中 a=97，b=98... 有了这个初始序列，我们就可以递归地探索候选项，这使我们得到 exploreCandidate 递归函数。

首先，我们要确保当前成本不是我们要查找的值。如果是，我们会立即离开，甚至不会评估候选人的后续迭代。我们要这样做是因为我们正在寻找按字典顺序排列的最小元素，并且不会要求我们提供有关所有候选者的信息。
如果成本条件不满足（成本 < K），我们需要继续探索我们的候选者，但不是针对整个矩阵，而是针对与最后一个字符对应的行。那么我们会遇到两种情况：

满足成本条件(cost = K)：如果在递归的某个点成本等于我们的值K，那么这个字符串是有效的，因为它将是我们遇到的第一个，我们想要return它并完成执行。
成本无效（成本>K）：如果当前成本大于K，那么我们需要中止这个分支，看看其他分支是否更幸运。返回一个布尔值会很好，但是因为我们想要输出一个字符串（或者可能不输出，取决于语句），一个选项可以是 return 一个字符串并使用“00”作为我们的“假”值，让我们知道成本条件是否已经满足。其他选项可以是 returning 布尔值并使用输出参数（通过引用传递）来包含输出字符串。

编辑： 提供的代码假定正的非零成本。如果某些成本为零，您可能会遇到无限递归，因此您需要在递归函数中添加更多约束。

Answer 2

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

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

b) 如果在 'a' 中找不到，则移至下一个字母。

Recurse/backtrack 可以这样完成：

以字母开头和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;
}

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

Given an integer K and a matrix of size t x t. construct a string s consisting of first t lowercase english letters such that the total cost of s is K

c++

algorithm

stl

vector

data-structures