0-1背包問題實作及Leetcode 132

0-1背包問題

• 問題描述

給定一組多個（n）物品，每種物品都有自己的重量（ w i w_i wi​）和價值（ v i v_i vi​），在限定的總重量/總容量（C）内，選擇其中若幹個（也即每種物品可以選0個或1個），設計選擇方案使得物品的總價值最高。

• 思路：

  定義問題dp(i, W)為前i個物品中，選擇的重量不超過W。對于第i個物品，要麼不選；要沒選，是以dp公式為：

  dp(i, W) = max(dp(i-1, W), dp(i-1, W- W i W_i Wi​)+ v i v_i vi​)

• 代碼如下：

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 pprint
	pprint(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:
                    break
            for 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]