小编Joh*_*Lui的帖子

给定一组 n 个整数，将该集合分成两个大小分别为 n/2 的子集，以使两个子集之和的差异尽可能小。如果 n 为偶数，则两个子集的大小必须严格为 n/2；如果 n 为奇数，则一个子集的大小必须为 (n-1)/2，另一个子集的大小必须为 (n+1)/2 .

例如，让给定的集合为 {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}，集合的大小是 10。这个集合的输出应该是 {4, 100, 1, 23, 20} 和 {3, 5, -3, 89, 54}。两个输出子集的大小均为 5，并且两个子集中的元素总和相同（148 和 148）。另一个 n 是奇数的例子。让给定集合为 {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}。输出子集应该是 {45, -34, 12, 98, -1} 和 {23, 0, -99, 4, 189, 4}。两个子集中元素的总和分别为 120 和 121。

经过多次搜索，我发现这个问题是 NP-Hard。因此，多项式时间解是不可能的。但是，我在想这样的事情：

1. 将第一个子集初始化为第一个元素。
2. 将第二个子集初始化为第二个元素。
3. 然后根据哪个子集的大小较小以及哪个子集中缺少总和，我将插入下一个元素。

我猜以上可能会达到线性时间。

然而，这里给出的解决方案太复杂了：http : //www.geeksforgeeks.org/tug-of-war/。我无法理解。所以，我想问一下，我的解决方案是否正确？考虑到这是一个 NP-Hard 问题，我认为应该这样做吗？如果没有，有人可以非常简短地解释一下，所附链接上的代码究竟是如何工作的？谢谢！

下面是我正在使用的一些简单代码:

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    float f = 1.66f;
    int d = (int)f;
    double g = (double)d;
    cout.precision(6);
    cout<<g<<"\n";
}

我想要它打印,1.000000但它只打印1.但是,即使将int升级为double后,它是否会自动将其转换为整数值？

我正在阅读有关静态内存分配和动态内存分配的内容.静态内存基本上是在堆栈上分配int a = 2;空间的地方a.但是,如果我这样做,int * a = new int; *a = 3这里的内存是在堆上分配的.但是,前者也可以称为自动内存分配吗？谢谢!

因此，我通过以下方法以迭代方式实现了DFS：

void dfsiter (graph * mygraph, int foo, bool arr[])
{
    stack <int> mystack;
    mystack.push(foo);
    while (mystack.empty() == false)
    {
        int k = mystack.top();
        mystack.pop();
        if (arr[k] == false)
        {
            cout<<k<<"\t";
            arr[k] = true;
            auto it = mygraph->edges[k].begin();
            while (it != mygraph->edges[k].end())
            {
                if (arr[*it] == false)
                {
                    mystack.push(*it);
                }
                it++;
            }

        }
    }
}

上面的代码可以正常工作。现在，我想使用上面的代码（迭代DFS）在无向图中检测循环。现在，我读到了，If an unexplored edge leads to a node visited before, then the graph contains a cycle.因此，我只想问你，我如何准确地跟踪所有这些？

我已经把我的图表变成这样：

class graph
{
    public:
    int vertices; …

#include <stdio.h>

int main(void) {
int i = -3, j = 2, k = 0, m;
m = ++i && ++j || ++k;
printf("%d %d %d %d\n",i,j,k,m);
    return 0;
}

我试图了解C中运算符的关联性和优先级.这里,输出结果是-2 3 0 1,但我认为输出应该是-2 3 1 1因为k也是预先递增的.为什么那不是答案？谢谢!

我正在阅读本文档中提到的Problem1(Part-b):

找到二进制最小堆的最小元素需要对数时间: T/F？

应该是这样,因为当我们构造一个最大堆时,时间复杂度O(logn)就像这里提到的那样.

同样,如果我构造一个min-heap,它应该是O(logn).min heap类似于max-heap,它只是在C++中,默认情况下构造了一个最大堆,我们将不得不为min-heap编写一个自定义比较器.然后,有什么区别？

所以,我试图在有向图中使用DFS找到一个循环.现在,我知道如果图形的拓扑排序不可能,那么图形包含一个循环.我为拓扑排序做了以下算法.我不知道我应该在哪里修改这个代码,以return true或false和检查,如果我的图包含一个周期或没有.这是我使用的算法:

DFS-Loop (Graph G)

1. Mark all vertices as unexplored.
2. Set label = n // number of vertices
3. For each vertex V (belonging to) G
   -- If V not yet explored,
   -- DFS (G,V)
4. Set f(V) = current_label // here, f(V) is basically the position of V in the ordering
5. current_label-- 

Where DFS(G,V) will be something like: 

1. Mark V as explored.
2. For every vertex K belonging to Adj.(V)
   -- …

我有一个 Djikstra 算法的工作实现，它计算任意两个节点之间的最短路径的长度。但如果我需要找到实际的路径，我该如何打印它呢？谢谢！

void djikstra( graph * mygraph )
{
    int dist[100] = {INT_MAX};
    int i;
    //int parent[mygraph->vertices] = {-99};
    for ( i = 0; i < 100; i++ )
        dist[i] = INT_MAX;
    bool arr[100];
    for ( i = 0; i < 100; i++ )
        arr[i] = false;
    int foo;
    cout<<"Enter the source vertex\n";
    cin>>foo;
    dist[foo] = 0;  
    vector<int> bar;
    while (bar.size() != mygraph->vertices)
    {
        int node = findmin(dist,mygraph->vertices,arr);
        arr[node] = true; // so that again and again same node …

我有以下代码：

int main(int argc, char** argv)
{
    cv::CommandLineParser parser(argc, argv,
            "{eyes||}{nose||}{mouth||}{help h||}");
    if (parser.has("help"))
    {
        help();
        return 0;
    }
    input_image_path = parser.get<string>(0);
    face_cascade_path = parser.get<string>(1);
    eye_cascade_path = parser.has("eyes") ? parser.get<string>("eyes") : "";
    nose_cascade_path = parser.has("nose") ? parser.get<string>("nose") : "";
    mouth_cascade_path = parser.has("mouth") ? parser.get<string>("mouth") : "";
    if (input_image_path.empty() || face_cascade_path.empty())
    {
        cout << "IMAGE or FACE_CASCADE are not specified\n";
        return 1;
    }
    // Load image and cascade classifier files
    Mat image;
    image = imread(input_image_path);

当我按如下方式运行代码时： ./code help

或者作为，

./code eyes: …

因此,我正在解决一个问题,该问题涉及对由开始和结束括号组成的给定序列的正确字符串进行排序.n括号序列由n "("s和n ")"s组成.

有效的括号序列定义如下:

您可以找到一种方法来重复擦除相邻的括号对,"()"直到它变空.

例如,"(())"是一个有效的括号,你可以在第二和第三个位置擦除它"()",然后你就可以将它变为空. ")()("不是有效的括号.现在,我想知道如何对给定长度的生成的括号序列进行排序,使得具有最大开括号的那些字符串开头,如果两个字符串在开头有相同数量的左括号,那么,在遍历两者时首先打印字符串,以第一个开口括号为准.例如,对于n=3,排序的序列将是,

((()))  // 3 opening in a row and hence first

(()()) // 2 opening (same as the one which is below this one) but has a opening bracket first

(())()

()(())

()()()