dp算法篇Day7

**DP算法篇 Day7**

在前面的几天里，我们已经学习了DP算法的基本概念、动态规划表格的建立以及如何使用DP解决一些经典的问题。今天，我们将继续深入探讨DP算法的应用，特别是关于背包问题和最长上升子序列问题。

**1. 背包问题**

背包问题是一类经典的DP问题，它涉及到在一个背包中放入尽可能多的物品，而这些物品的重量或价值都有限制。我们可以将其视为一种选择问题，每个物品都有两种选择：放入背包还是不放。

**1.10/1 背包问题**

在这个版本中，我们只能选择一次背包中的物品，而不能多次选择同一个物品。假设我们有 n 个物品，每个物品的重量为 w_i，价值为 v_i，我们需要在背包容量为 W 的情况下放入尽可能多的物品。

def knapsack(W, wt, val, n):
 K = [[0 for w in range(W +1)] for i in range(n +1)]

 # Build table K[][] in bottom up manner for i in range(n +1):
 for w in range(W +1):
 if i ==0 or w ==0:
 K[i][w] =0 elif wt[i -1] <= w:
 K[i][w] = max(val[i -1] + K[i -1][w - wt[i -1]], K[i -1][w])
 else:
 K[i][w] = K[i -1][w]

 return K[n][W]

def knapsack(W, wt, val, n):
 K = [[0 for w in range(W +1)] for i in range(n +1)]

 # Build table K[][] in bottom up manner for i in range(1, n +1):
 for w in range(1, W +1):
 if wt[i -1] <= w:
 K[i][w] = max(val[i -1] + K[i -1][w - wt[i -1]], K[i -1][w])
 else:
 K[i][w] = K[i -1][w]

 return K[n][W]

def longest_ascending_subsequence(arr):
 n = len(arr)
 dp = [1] * n for i in range(1, n):
 for j in range(i):
 if arr[i] > arr[j]:
 dp[i] = max(dp[i], dp[j] +1)

 return max(dp)