0-1背包问题实现及Leetcode 132

本文主要是介绍0-1背包问题实现及Leetcode 132，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0-1背包问题

• 问题描述

给定一组多个（n）物品，每种物品都有自己的重量（$w_i$）和价值（$v_i$），在限定的总重量/总容量（C）内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高。

• 思路：
  定义问题dp(i, W)为前i个物品中，选择的重量不超过W。对于第i个物品，要么不选；要没选，因此dp公式为：
  dp(i, W) = max(dp(i-1, W), dp(i-1, W-$W_i$)+$v_i$)

• 代码如下：

def package_01(n, weights, values, C):dp = [[0]*(C+1) for _ in range(n+1)]for i in range(1, n+1):for j in range(1, C+1):dp[i][j] = dp[i-1][j]if j-weights[i-1] > 0:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])from pprint import pprintpprint(dp)return dp[n][C]n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
print(package_01(n, w, v, c))

• 输出结果

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 6, 6, 6, 6, 6, 6, 6, 6],[0, 0, 0, 6, 6, 9, 9, 9, 9, 9, 9],[0, 0, 0, 6, 6, 9, 9, 9, 9, 11, 11],[0, 0, 0, 6, 6, 9, 9, 9, 10, 11, 13],[0, 0, 0, 6, 6, 9, 9, 12, 12, 15, 15]]
15

leetcode 132

• 问题描述

Given a string s, partition s such that every substring of the partition is a palindrome.Return the minimum cuts needed for a palindrome partitioning of s.Example:Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

• 思路见注释，代码如下：

class Solution:def minCut(self, s):""":type s: str:rtype: int"""n = len(s)dp = [i-1 for i in range(n+1)]for mid in range(0, n):for offset in range(0, n): # 奇数长度回文if mid-offset >= 0 and mid+offset < n and s[mid-offset] == s[mid+offset]:dp[mid+offset+1] = 0 if mid-offset == 0 else min(dp[mid+offset+1], 1+dp[mid-offset])else:breakfor offset in range(0, n): # 偶数长度回文if mid-offset >= 0 and mid+offset+1 < n and s[mid-offset] == s[mid+offset+1]:dp[mid+offset+2] = 0 if mid-offset == 0 else min(dp[mid+offset+2], 1+dp[mid-offset])else:break
#         print(dp)return dp[-1]

这篇关于0-1背包问题实现及Leetcode 132的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---