动态编程将问题分解为较小的子问题，解决了每个子问题并将这些子问题的解决方案存储在数组（或类似数据结构）中，因此每个子问题只计算一次。

它既是数学优化方法又是计算机编程方法。

优化问题寻求最大或最小的解决方案。一般规则是，如果遇到在O（2n）时间内解决初始算法的问题，则最好使用动态编程来解决。

为什么将动态编程称为动态编程？

理查德·贝尔曼（Richard Bellman）在1950年代发明了DP。Bellman之所以将其命名为Dynamic Programming，是因为当时RAND（他的雇主）不喜欢数学研究，也不想为其提供资金。他将其命名为“动态编程”，以掩盖他确实在从事数学研究的事实。

Bellman在他的自传《飓风之眼：自传》（1984，第159页）中解释了动态编程一词的原因。他解释说：

“我（1950年）的秋天季度在兰德公司度过。

我的第一个任务是为多阶段决策流程找到一个名称。一个有趣的问题是，动态编程的名称从何而来？

1950年代不是数学研究的好年头。我们在华盛顿有一位非常有趣的绅士，名叫威尔逊。他曾任国防部长，实际上对病理学一词有病态的恐惧和仇恨。我不是在轻率地使用这个词。我正在精确地使用它。

如果人们在他的面前使用“研究”一词，他的脸就会闷闷不乐，他会变成红色，并且会变得暴力。您可以想象他对数学一词的感觉。兰德公司（RAND Corporation）受雇于空军，而空军实质上是由威尔逊（Wilson）担任老板。因此，我觉得我必须做些事情来保护威尔逊和空军免受事实的困扰，因为我实际上是在RAND公司内部从事数学工作。我可以选择什么标题，什么名字？首先，我对计划，决策，思考感兴趣。但是出于各种原因，规划并不是一个好词。因此，我决定使用“编程”一词。我想了解一下这是动态的，这是多阶段的，这是随时间变化的。我想，让我们用一块石头杀死两只鸟。让我们以古典物理意义上具有绝对精确意义的单词（即动态的）为例。它也有一个非常有趣的性质，作为形容词，这是不可能在贬义的意义上使用“动态”一词的。尝试考虑一些可能赋予其贬义性的组合。不可能。因此，我认为动态编程是一个好名字。这是连国会议员都无法反对的东西。因此，我将它用作活动的保护伞。” 这是连国会议员都无法反对的东西。因此，我将它用作活动的保护伞。” 这是连国会议员都无法反对的东西。因此，我将它用作活动的保护伞。”

什么是子问题？

子问题是原始问题的较小版本。让我们来看一个例子。使用以下等式：

1 + 2 + 3 + 41个+2个+3+4

我们可以将其分解为：

1 + 21个+2个

3 + 43+4

一旦解决了这两个较小的问题，就可以将解决方案添加到这些子问题中，以找到整体问题的解决方案。

请注意，这些子问题如何将原始问题分解为构成解决方案的组件。这是一个小例子，但是很好地说明了动态编程的美。如果我们将问题扩展到100的数字上，则更清楚了我们为什么需要动态编程。举个例子：

6 + 5 + 3 + 3 + 2 + 4 + 6 + 56+5+3+3+2个+4+6+5

我们有 6 + 56+5两次。第一次看到它，我们就会锻炼6 + 56+5。当我们第二次看到它时，我们会自省：

“啊，6 +5。我以前见过。是11点！”

在动态编程中，我们存储问题的解决方案，因此我们无需重新计算。通过为每个子问题找到解决方案，我们可以解决原始问题本身。

*备忘*是存储解决方案的行为。

动态编程中的记忆是什么？

让我们来看看为什么存储解决方案的答案才有意义。我们将研究一个著名的问题，斐波那契数列。通常在“分而治之”中解决此问题。

有3个主要部分分而治之：

1. **将**问题分解为相同类型的较小子问题。
2. **征服**-递归解决子问题。
3. **组合**-组合所有子问题以创建原始问题的解决方案。

动态编程在步骤2的基础上又增加了一个步骤。这就是备忘录。

斐波那契数列是一个数字序列。它是最后一个数字+当前数字。我们从1开始。

1 + 0 = 11个+0=1个

1 +1 = 21个+1个=2个

2 +1 = 32个+1个=3

3 + 2 = 53+2个=5

5 + 3 = 85+3=8

在Python中，这是：

def F(n):
    if n == 0 or n == 1:
    return n
    else:
    return F(n-1)+F(n-2)

如果您不熟悉递归，那么我为您撰写了一篇博客文章，您应该首先阅读。

让我们计算F（4）。在执行树中，如下所示：

我们计算F（2）两次。在较大的输入（例如F（10））上，重复次数增加。动态编程的目的是避免两次计算相同的事物。

无需两次计算F（2），我们将解存储在某个地方，只计算一次。

我们将解决方案存储在一个数组中。F [2] =1。下面是一些Python代码，用于使用动态编程计算斐波那契数列。

def fibonacciVal(n):
    memo[0], memo[1] = 0, 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

如何识别动态编程问题

从理论上讲，动态编程可以解决所有问题。问题是：

“什么时候应该使用动态编程解决这个问题？”

对于*难以解决的*和*难以解决的*问题之间的问题，我们应该使用动态编程。

可解决的问题是可以在多项式时间内解决的问题。这是说我们可以快速解决问题的一种奇特的方式。二进制搜索和排序都非常快。棘手的问题是那些在指数时间内运行的问题。太慢了 棘手的问题是只能通过对每个单独的组合进行暴力破解才能解决的问题（ NP难题）。

当我们看到类似这样的字词时：

“最短/最长，最小/最大，最小/最大，最小/最大，“最大/最小”

我们知道这是一个优化问题。

动态编程算法正确性的证明通常是不言而喻的。其他算法策略通常很难证明是正确的。因此，更容易出错。

当我们看到这些类型的术语时，问题可能会要求一个特定的数字（“查找最小数量的编辑操作”），也可能会要求一个结果（“查找最长的公共子序列”）。后一种类型的问题很难识别为动态编程问题。如果听起来像是优化，则动态编程可以解决问题。

想象一下，我们发现了一个问题，这是一个优化问题，但是我们不确定是否可以使用动态编程来解决。首先，确定我们要优化的内容。一旦意识到要优化的内容，就必须决定进行优化的难易程度。有时候，贪婪的方法足以提供最佳解决方案。

动态编程采用蛮力方法。它确定重复的工作，并消除重复。

在我们甚至开始将问题计划为动态编程问题之前，请考虑一下蛮力解决方案的外观。在蛮力解决方案中是否重复了子步骤？如果是这样，我们尝试将问题想象为动态编程问题。

掌握动态编程就是要了解问题。列出所有可能影响答案的输入。确定了所有输入和输出后，请尝试确定问题是否可以分解为子问题。如果我们可以确定子问题，则可以使用动态编程。

然后，弄清楚什么是复发并解决它。当我们试图找出复发时，请记住，无论我们写出什么复发都必须帮助我们找到答案。有时答案将是重复发生的结果，有时我们必须通过查看重复发生的一些结果来获得结果。

动态编程可以解决许多问题，但这并不意味着没有更有效的解决方案。用动态编程解决问题似乎很神奇，但是请记住，动态编程只是一种聪明的蛮力。有时它能带来很好的回报，有时却仅能起到一点作用。

如何使用动态编程解决问题

现在我们已经了解了什么是动态编程以及它通常如何工作。让我们看一下如何为问题创建动态编程解决方案。我们将使用加权间隔调度问题探索动态规划的过程。

假设您是干洗店的所有者。您有n位顾客进来给您洗衣服。您一次只能清洗一个客户的衣服堆（PoC）。每堆衣服i必须在预定的开始时间清洗s_is一世​ 和一些预定的完成时间 _F一世​。

每堆衣服都有相关的价值， v_iv一世​，取决于它对您的业务有多重要。例如，某些顾客可能要花更多钱才能更快地洗衣服。也许有些人回头客，而您希望他们开心。

作为该干洗店的所有者，您必须确定最佳的服装搭配时间表，以使这一天的总价值最大化。该问题是加权间隔调度问题的重新措辞。

现在，您将看到解决动态编程问题的4个步骤。有时，您可以跳过一个步骤。有时，您的问题已经被很好地定义了，您无需担心前几个步骤。

步骤1.写出问题

拿一张纸。写出：

• 问题是什么？
• 有哪些子问题？
• 解决方案大致是什么样的？

在干洗店问题中，让我们将子问题简单化。我们要确定的是每堆衣服的最大值计划，以便按开始时间对衣服进行分类。

为什么按开始时间排序？好问题！我们想跟踪当前正在运行的进程。如果我们按完成时间排序，那对我们来说就没有多大意义了。我们可以有2个具有相似的完成时间，但有不同的开始时间。时间从开始到结束都以线性方式移动。如果我们有成堆的衣服从下午1点开始，我们知道在下午1点穿上衣服。如果我们有一堆衣服要在下午3点结束，那么我们可能需要在下午12点穿好衣服，但是现在是下午1点。

我们可以找到桩的最大价值计划 n-1ñ-1个一直到 然后n-2ñ-2个一直到 等等。通过找到每个子问题的解决方案，我们可以解决原始问题本身。桩号1到n的最大值计划。子问题可以用来解决原始问题，因为它们是原始问题的较小版本。

对于间隔调度问题，我们可以解决的唯一方法是对问题的所有子集进行强行强制，直到找到最佳问题为止。我们要说的是，我们将暴力行为一分为二，而不是一味地蛮力强行。我们从蛮力n-1ñ-1个一直到 然后我们对n-2ñ-2个一直到 最后，我们有许多较小的问题，可以动态解决。我们希望为子问题构建解决方案，以使每个子问题都基于先前的问题。

2.数学递归

我知道，数学很烂。如果您在这里与我裸露，您会发现这并不难。数学递归用于：

定义分治法（动态编程）技术的运行时间

重现也用于定义问题。如果很难将子问题转化为数学，则可能是错误的子问题。

创建数学递归有两个步骤：

1：定义基本情况

基本案例是问题的最小可能面额。

创建重复周期时，请问自己以下问题：

“我在第0步做出什么决定？”

它不必为0。基本情况是问题的最小可能面额。我们通过斐波那契数列看到了这一点。基数是：

• 如果n == 0或n == 1，则返回1

重要的是要知道基本案例在哪里，这样我们就可以创建递归。对于我们的问题，我们有一个决定要做出：

• 把那堆衣服洗干净

或者

• 今天不要洗那堆衣服

如果n为0，也就是说，如果我们有0 PoC，那么我们什么也不做。我们的基本情况是：

如果n == 0，则返回0

2：我在步骤n会做出什么决定？

现在我们知道基本情况是什么，如果我们在步骤n中，我们该怎么做？到目前为止，每堆衣服都符合日程安排。兼容表示开始时间在当前正在清洗的那堆衣服的完成时间之后。该算法有2个选项：

1. 洗那堆衣服
2. 不要洗那堆衣服

我们知道在基本情况下会发生什么，以及在其他情况下会发生什么。现在，我们需要找出算法需要向后（或向前）前进的信息。

“如果我的算法在步骤i中，则它需要什么信息来决定在步骤i + 1中该做什么？”

为了在两个选项之间做出决定，算法需要知道下一个兼容的PoC（衣服堆）。给定堆p的下一个兼容PoC是PoC n，使得s_nsñ​ （PoC n的开始时间）发生在 f_pFp​（PoC p的完成时间）。和...之间的不同s_nsñ​ 和 f_pFp​ 应该最小化。

用英语，想象我们有一台洗衣机。我们在13:00放了一堆衣服。我们的下一堆衣服从13:01开始。我们无法打开洗衣机并放入从13:00开始的洗衣机。我们下一堆兼容的衣服是在当前要清洗的衣服的完成时间之后开始的衣服。

“如果我的算法在步骤i中，则它需要什么信息来决定在步骤i-1中该做什么？”

该算法需要了解未来的决策。由PoC i到n决定是否运行PoC i-1的程序。

现在，我们已经回答了这些问题，我们开始在脑海中形成一个反复出现的数学决定。如果没有，那也没关系，随着我们面临更多的问题，编写重复代码变得更加容易。

这是我们的重复周期：

$$ OPT（i）= \ begin {cases} 0，\ quad \ text {如果i = 0} \\ max {v_i + OPT（next [i]），OPT（i + 1）}，\ quad \ text {if n> 1} \ end {cases \\ end {cases} $$

让我们详细探讨是什么导致这种数学递归。OPT（i）表示PoC i到n的最大值计划，以使PoC按开始时间排序。OPT（i）是我们先前的子问题。

我们从基本情况开始。所有复发都需要在某个地方停止。如果调用OPT（0），则返回0。

为了确定OPT（i）的值，有两种选择。我们希望最大程度地利用这些选项来实现我们的目标。我们的目标是为所有成堆衣服提供最大价值计划。一旦选择了在步骤i中获得最大结果的选项，我们便将其值记为OPT（i）。

在数学上，两个选项-运行或不运行PoC i，表示为：

v_i + OPT（next [n]）v一世​+O P T （n e x t [ n ] ）

这表示运行PoC i的决定。它将从PoC i获得的值添加到OPT（next [n]），其中next [n]代表继PoC i之后的下一个兼容服装。当我们将这两个值加在一起时，我们得到了从i到n的最大值调度，因此如果我运行，它们将按开始时间排序。

在这里按开始时间排序，因为next [n]是v_i之后的那个，因此默认情况下，它们按开始时间排序。

OPT（i +1）ø P Ť （我+1 ）

如果我们决定不运行i，那么我们的值就是OPT（i + 1）。无法获得该值。OPT（i + 1）给出从i + 1到n的最大值计划，以便按开始时间对它们进行排序。

3.确定存储阵列的尺寸及其填充方向

解决动态规划问题的方法是OPT（1）。我们可以将解决方案写为PoC 1到n的最大值计划，以便按开始时间对PoC进行排序。这与“ PoC i至n的最大价值计划”齐头并进。

从步骤2：

OPT（1）= max（v_1 + OPT（next [1]），OPT（2））O P T （1 ）=中号一个X （v1个​+O P T （n e x t [ 1 ] ），O P T （2 ））

回到前面的斐波那契数，我们的动态编程解决方案依赖于这样的事实，即0到n-1的斐波那契数已经被记忆。也就是说，要找到F（5），我们已经记忆了F（0），F（1），F（2），F（3），F（4）。我们想在这里做同样的事情。

我们遇到的问题是弄清楚如何填写备忘录表。在调度问题中，我们知道OPT（1）依赖于OPT（2）和OPT（next [1]）的解决方案。由于排序，PoC 2和next [1]在PoC 1之后具有开始时间。我们需要从OPT（n）到OPT（1）填写我们的备注表。

我们可以看到我们的数组是一维的，从1到n。但是，如果我们看不到可以采用其他方法解决。数组的维数等于OPT（x）所依赖的变量的数量和大小。在我们的算法中，我们有OPT（i）-一个变量i。这意味着我们的数组将是一维的，其大小将为n，因为有n堆衣服。

如果我们知道n = 5，那么我们的记忆数组可能看起来像这样：

memo = [0, OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

0也是基本情况。memo [0] = 0，根据我们之前的介绍。

4.编码我们的解决方案

在编写动态编程解决方案时，我喜欢阅读重复并尝试重新创建它。我们的第一步是将数组初始化为大小（n + 1）。在Python中，我们不需要这样做。但是，如果您使用其他语言，则可能需要这样做。

我们的第二步是设置基本情况。

通过工作[i]来寻找利润。我们需要找到与job [i]不冲突的最新工作。想法是使用二进制搜索来找到最新的不冲突的作业。我已经从此处复制了代码，但已对其进行了编辑。

首先，让我们定义什么是“工作”。正如我们所看到的，一份工作由三部分组成：

    # Class to represent a job 
class Job: 
    def __init__(self, start, finish, profit): 
        self.start = start 
        self.finish = finish 
        self.profit = profit 

开始时间，完成时间以及运行该工作的总利润（收益）。

我们要编程的下一步是时间表。

# The main function that returns the maximum possible 
# profit from given array of jobs
def schedule(job): 
    # Sort jobs according to start time 
    job = sorted(job, key = lambda j: j.start) 

    # Create an array to store solutions of subproblems. table[i] 
    # stores the profit for jobs till arr[i] (including arr[i]) 
    n = len(job) 
    table = [0 for _ in range(n)] 

    table[0] = job[0].profit

早先，我们了解到表格是一维的。我们按开始时间对作业进行排序，创建此空表并将表[0]设置为作业[0]的利润。由于我们已经按照开始时间进行了排序，因此第一个兼容的作业始终是job [0]。

我们的下一步是使用我们先前学到的重复记录来填写条目。为了找到下一个兼容的作业，我们使用了二进制搜索。在稍后发布的完整代码中，将包括此内容。现在，让我们担心了解算法。

如果下一个兼容的作业返回-1，则表示索引i之前的所有作业都与其冲突（因此无法使用）。Inclprof表示我们将该项包含在最大值集中。然后将其存储在table [i]中，以便稍后可以再次使用此计算。

    # Fill entries in table[] using recursive property 
    for i in range(1, n): 

        # Find profit including the current job 
        inclProf = job[i].profit 
        l = binarySearch(job, i) 
        if (l != -1): 
            inclProf += table[l]; 

        # Store maximum of including and excluding 
        table[i] = max(inclProf, table[i - 1]) 

然后，我们的最后一步是将所有项目的利润返还至n-1。

    	return table[n-1] 

完整的代码如下所示：

    # Python program for weighted job scheduling using Dynamic 
    # Programming and Binary Search 
    
    # Class to represent a job 
    class Job: 
    	def __init__(self, start, finish, profit): 
    		self.start = start 
    		self.finish = finish 
    		self.profit = profit 
    
    
    # A Binary Search based function to find the latest job 
    # (before current job) that doesn't conflict with current 
    # job. "index" is index of the current job. This function 
    # returns -1 if all jobs before index conflict with it. 
    def binarySearch(job, start_index): 
    	# https://en.wikipedia.org/wiki/Binary_search_algorithm
    
    	# Initialize 'lo' and 'hi' for Binary Search 
    	lo = 0
    	hi = start_index - 1
    
    	# Perform binary Search iteratively 
    	while lo <= hi: 
    		mid = (lo + hi) // 2
    		if job[mid].finish <= job[start_index].start: 
    			if job[mid + 1].finish <= job[start_index].start: 
    				lo = mid + 1
    			else: 
    				return mid 
    		else: 
    			hi = mid - 1
    	return -1
    
    # The main function that returns the maximum possible 
    # profit from given array of jobs 
    def schedule(job): 
    	# Sort jobs according to start time 
    	job = sorted(job, key = lambda j: j.start) 
    
    	# Create an array to store solutions of subproblems. table[i] 
    	# stores the profit for jobs till arr[i] (including arr[i]) 
    	n = len(job) 
    	table = [0 for _ in range(n)] 
    
    	table[0] = job[0].profit; 
    
    	# Fill entries in table[] using recursive property 
    	for i in range(1, n): 
    
    		# Find profit including the current job 
    		inclProf = job[i].profit 
    		l = binarySearch(job, i) 
    		if (l != -1): 
    			inclProf += table[l]; 
    
    		# Store maximum of including and excluding 
    		table[i] = max(inclProf, table[i - 1]) 
    
    	return table[n-1] 
    
    # Driver code to test above function 
    job = [Job(1, 2, 50), Job(3, 5, 20), 
    	Job(6, 19, 100), Job(2, 100, 200)] 
    print("Optimal profit is"), 
    print(schedule(job))
    

恭喜！just我们已经编写了第一个动态程序！现在我们已经弄湿了，让我们逐步解决另一种类型的动态编程问题。

背包问题

想象你是一个罪犯。呆呆的聪明。您闯入比尔·盖茨的豪宅。哇，好吧！这是几间房？他的洗衣机室比我的整个房子都要大？？？好吧，该停止分心了。你带了一个小袋子。背包-如果可以的话。

您只能容纳这么多。让我们给它一个任意数字。袋子将支撑重物15，但仅此而已。我们想要做的是最大化我们能赚多少钱，bb。

贪婪的方法是挑选可以放入袋子的具有最高价值的物品。让我们尝试一下。我们要偷比尔·盖茨的电视。4000英镑？好的。但是他的电视重15磅。所以……我们带着4000英镑离开。

TV = (£4000, 15)
# (value, weight)

比尔·盖茨（Bill Gates）有很多手表。假设他有2块手表。每只手表重5英镑，每只价值2250英镑。当我们同时偷走这两者时，我们将获得£4500的权重为10的收益。

watch1 = (£2250, 5)
watch2 = (£2250, 5)
watch1 + watch2
>>> (£4500, 10)

在贪婪的方法中，我们不会首先选择这些手表。但是对于我们人类来说，选择具有较高价值的较小物品是有意义的。贪婪方法不能最佳地解决{0,1}背包问题。{0，1}表示我们要么拿走整个物品{1}，要么不拿走{0}。但是，动态编程可以最佳地解决{0，1}背包问题。

解决此问题的简单方法是考虑所有项目的所有子集。对于比尔·盖茨的每一个单一组合，我们都会计算出该组合的总重量和价值。

仅那些体重小于 W_ {max}w ^中号一个X​被考虑。然后，我们选择具有最高价值的组合。这是一场灾难！这需要多长时间？比尔·盖茨（Bill Gates）的家很早就回到家了，甚至还不到您的三分之一！在Big O中，此算法需要O（n ^ 2）Ø （ñ2个） 时间。

您可以看到我们已经对解决方案和问题有一个大概的了解，而不必将其写下来！

{0，1}背包问题背后的数学

想象一下，我们在比尔·盖茨家中列出了所有物品。我们从一些保险单中偷了它。现在，考虑未来。该问题的最佳解决方案是什么？

我们有一个子集L，这是最佳解决方案。L是S的子集，S包含Bill Gates的所有东西。

我们选择一个随机项目N。L包含N或不包含N。如果不使用N，则该问题的最佳解决方案与{1，2，…，N-1}1 ，2 ，…，ñ-1个。假设Bill Gates的资料按以下顺序排序价值/重量v一个升ü ë /瓦特ë我克ħ吨。

假设原始问题的最优值不是子问题的最优值。如果我们有较小问题的次优问题，那么我们就会有一个矛盾-我们应该对整个问题有一个最优问题。

如果L包含N，则该问题的最佳解与 {1,2,3，...，N-1}1 ，2 ，3 ，…，ñ-1个。我们知道项目在其中，因此L已经包含N。为了完成计算，我们将重点放在其余项目上。我们找到了其余项目的最佳解决方案。

但是，我们现在有了一个新的最大允许重量 W_ {max}-W_nw ^中号一个X​-w ^ñ​。如果解决方案中包含项目N，则总重量现在就是最大重量（项目背包中已经带走的物品N）。

这是两种情况。项目N是否处于最佳解决方案中，或者不是。

如果物品N的重量大于 W_ {max}w ^中号一个X​，则无法将其包括在内，因此情况1是唯一的可能性。

为了更好地定义此递归解决方案，让 S_k = {1,2，…，k}小号ķ​=1 ，2 ，…，ķ 和 S_0 = \空集小号0​=∅

令B [k，w]为使用的子集获得的最大总收益S_k小号ķ​。总重量不超过w。

然后我们为每个定义B [0，w] = 0 w \ le W_ {max}w≤w ^中号一个X​。

那么我们期望的解是B [n， W_ {max}w ^中号一个X​]。

OPT（i）= \ begin {cases} B [k-1，w]，\ quad \ text {如果w <} w_k \\ max {B [k-1，w]，b_k + B [k-1， w-w_k]}，\ \ quad \ text {otherwise} \ end {cases}O P T （i ）={乙[ ķ-1 ，w ^ ] ，如果w <  wķ​中号一个X乙[ ķ-1 ，w ^ ] ，bķ​+乙[ ķ-1 ，w-wķ​]， 否则​

背包问题列表

好吧，拿出一些笔和纸。不完全是。事情将很快变得令人困惑。该备忘录表是二维的。我们有以下项目：

if j < wt[i]:

if j < wt[i]:
	T[i][j] = T[i - 1][j]
else:
	# weight of i >= j
	T[i][j] = max(val[i] + t[i - 1][j-wt(i), t[i-1][j])
	# previous row, subtracting the weight of the item from the total weight or without including ths item

# Returns the maximum value that can be put in a knapsack of 
# capacity W 
def knapSack(W , wt , val , n): 
	
	# Base Case 
	if n == 0 or W == 0: 
		return 0
	
	# If weight of the nth item is more than Knapsack of capacity 
	# W, then this item cannot be included in the optimal solution 
	if (wt[n-1] > W): 
		return knapSack(W , wt , val , n-1) 
	
	# return the maximum of two cases: 
	# (1) nth item included 
	# (2) not included 
	else: 
		return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), 
					knapSack(W , wt , val , n-1)) 
	
	
# To test above function 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val) 
print(knapSack(W , wt , val , n))
# output 220