背包问题

yingl · yingl · commit e4f6ffd70aa2 · 2016-08-09T15:31:16.000+08:00
diff --git a/backpack.py b/backpack.py
@@ -0,0 +1,24 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param m: An integer m denotes the size of a backpack
+    # @param A: Given n items with size A[i]
+    # @return: The maximum size
+    def backPack(self, m, A):
+        # write your code here
+        '''
+        动态规划，已m = 10，A = [3, 4, 8, 5]为例：
+        1. A[0] = 3, c[10] ... C[3] = 3
+        2. A[1] = 4
+          - c[10] = max(c[10 - 4] + 4, c[10]) = max(c[6] + 4, c[10]) = 7
+          - c[7] = c[8] = c[9] = 7
+          - c[6] = max(c[6 - 4] + 4, c[6]) = 4
+          - c[4] = c[5] = 4
+        c[i]表示大小为i的空间的最大容量，对于大小为k的物品，状态转移方程为：c[i] = max(c[i - k] + k, c[i])
+        '''
+        capacities = [0] * (m + 1)
+        if A:
+            for i in xrange(len(A)):
+                for j in xrange(m, A[i] - 1, -1):
+                    capacities[j] = max(capacities[j - A[i]] + A[i], capacities[j])
+        return capacities[-1]
