相关疑难解决方法(0)

我更喜欢尽可能少的正式定义和简单的数学.

我正在努力理解什么是不确定多项式时间问题和NP完全问题.我理解多项式时间可解决的问题,并在维基百科中看到NP问题.在阅读了这篇文章后,我试着想一些示例问题.据我了解,深度优先搜索的是无向的NP完全,因为每个决策都可以做出非决定性的(即如果我做出了错误的决定,我可以尝试其他选择)如果图表很大(cit是一个如果图形尺寸很小,则为多项式.)

任何人都可以用简单的例子简单地解释所有这些NP术语,而不需要使

我为你准备了一个脑筋急转弯 - 它并不像听起来那么简单,所以请阅读并尝试解决问题.在你问它是否是作业之前 - 它不是!我只想看看是否有一种优雅的解决方法.这是问题所在:

X号朋友想要去电影院并希望坐在最好的团体中.最好的情况是每个人坐在一起,最糟糕的情况是每个人都独自坐着.与更多群体相比,更少的群体更受欢迎.Ballanced组是优选的(3 + 3比4 + 2更优选).独自坐着是最不可取的.

输入是进入影院的人数,输出应该是整数数组的数组,其中包含:

• 有序组合(最优选的是第一个)
• 每组人数

以下是一些前往电影院的人数以及这些人可以坐下的首选组合列表:

• 1人:1
• 2人:2,1 + 1
• 3人:3 + 2 + 1,1 + 1 + 1
• 4人:4,2 + 2,3 + 1,2 + 1 + 1,1 + 1 + 1 + 1
• 5人:5,3 + 2,4 + 1,2 + 2 + 1,3 + 1 + 1,2 + 1 + 1 + 1,1 + 1 + 1 + 1 + 1
• 6人:6,3 + 3,4 + 2,2 + 2 + 2,5 + 1,3 …

更新:为了帮助澄清我的要求,我已经发布了一些可以解决问题的java代码.

前段时间我问一个问题,如何得到一个算法,打破了一组数字,当时的想法是给它编号列表(1,2,3,4,5)和共(10),它会找出每个将增加数的所有倍数达到总数('1*10'或' 1*1,1*2,1*3,1*4'或' 2*5'等等).这是我做过的第一次编程练习,所以它花了我一段时间才开始工作,但现在我想试着看看我是否可以扩展它.原问题中的人说它是可扩展的,但我对如何做到这一点感到困惑.递归部分是我在缩放组合所有结果的部分时遇到的区域(它所指的表是不可扩展的但是应用缓存我能够使它快速)

我有以下算法(伪代码):

//generates table
for i = 1 to k
    for z = 0 to sum:
        for c = 1 to z / x_i:
            if T[z - c * x_i][i - 1] is true:
                set T[z][i] to true

//uses table to bring all the parts together
function RecursivelyListAllThatWork(k, sum) // Using last k variables, make sum
    /* Base case: If we've assigned all the variables correctly, list …