状态转移方程:
P(i,W)表示如果只有i个物品,背包可容纳W重量情况下,的最优解
P(i,W) = max (P(i - 1,W),P(i - 1,W - A[ i ]) + A [ i ])
优化:
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 backPack1(self, m, A): """使用递归进行处理,自顶向下,空间复杂度O(n * m)""" # write your code here dp = [[-1] * len(A) for i in range(m + 1)] def helper(m, index): if dp[m][index] != -1: return dp[m][index] if m <= 0 or index < 0: return 0 if index == 0 and m >= A[0]: return A[0] if m >= A[index]: dp[m][index] = max(helper(m, index - 1), helper(m - A[index], index - 1) + A[index]) else: dp[m][index] = helper(m, index - 1) return dp[m][index] result = helper(m, len(A) - 1) return result def backPack2(self, m, A): """使用迭代的动态规划,自底向上""" dp = [[0] * (m + 1) for i in A] for i in range(1, m + 1): dp[0][i] = A[0] if i >= A[0] else 0 for i in range(1, len(A)): for j in range(1, m + 1): if j >= A[i]: dp[i][j] = max(dp[i - 1][j - A[i]] + A[i], dp[i - 1][j]) else: dp[i][j] = dp[i - 1][j] return dp[len(A) - 1][m] def backPack3(self, m, A): """ 优化空间复杂度,以上的代码理论上只需要使用两行数组就好了,dp[i][...] 和 dp[i - 1][...]这两行 """ pre = [0] * (m + 1) curr = [0] * (m + 1) for i in range(1, m + 1): pre[i] = A[0] if i >= A[0] else 0 for i in range(1, len(A)): for j in range(1, m + 1): if j >= A[i]: curr[j] = max(pre[j - A[i]] + A[i], pre[j]) else: curr[j] = pre[j] curr, pre = pre, curr return pre[m] def backPack4(self, m, A): """ 只使用一行数组,可以在pre的基础上,从右向左刷新数据,这样就可以利用上一个数组的内容了 同时增加了剪枝的条件 j < A[i] : break """ pre = [0] * (m + 1) for i in range(1, m + 1): pre[i] = A[0] if i >= A[0] else 0 for i in range(1, len(A)): #倒着遍历 for j in range(m, 0, -1): if j >= A[i]: pre[j] = max(pre[j - A[i]] + A[i], pre[j]) else: break return pre[m] nums = [988, 417, 92, 268, 313, 293, 530, 134, 311, 918, 355, 826, 94, 580, 793, 731, 320, 101, 612, 410, 640, 393, 278, 660, 842, 543, 130, 793, 407, 797, 176, 685, 521, 776, 473, 756, 597, 376, 615, 547, 310, 579, 177, 450, 842, 677, 640, 687, 515, 178, 583, 271, 161, 401, 595, 354, 868, 773, 74, 178, 626, 192, 747, 716, 148, 499, 654, 584, 886, 127, 171, 121, 563, 222, 802, 818, 546, 230, 50, 470, 134, 689, 276, 948, 261, 794, 680, 674, 444, 580, 313, 125, 473, 940, 888, 899, 75, 243, 792, 568, 173, 872, 376, 513, 719, 302, 96, 369, 163, 314, 61, 58, 181, 262, 85, 432, 695, 728, 759, 969, 305, 826, 345, 388, 79, 953, 838, 648, 692, 240, 645, 675, 352, 257, 711, 536, 272, 779, 99, 332, 909, 175, 711, 561, 170, 390, 814, 820, 383, 690, 460, 664, 395, 831, 420, 876, 413, 824, 605, 812, 581, 343, 518, 213, 236, 957, 273, 707, 561, 922, 681, 985, 282, 493, 299, 261, 382, 560, 263, 361, 936, 746, 224, 509, 578, 149, 993, 989, 730, 354, 587, 662, 184, 924, 70, 422, 344, 794, 459, 277, 286, 572, 970, 947, 665, 287, 675, 239, 208, 596, 907, 685, 714, 544, 90, 706, 305, 538, 558, 182, 798, 924, 211, 245, 613, 416, 63, 514, 830, 641, 421, 858, 238, 968, 77, 612, 864, 524, 988, 302, 332, 402, 751, 421, 992, 94, 836, 953, 445, 600, 197, 894, 195, 630, 792, 762, 844, 993, 80, 186, 471, 725, 265, 132, 939, 509, 653, 347, 837, 877, 601, 941, 418, 784, 677, 351, 673, 734, 790, 465, 965, 600, 267, 478, 868, 927, 825, 697, 400, 116, 708, 520, 792, 129, 448, 464, 336, 570, 888, 100, 352, 300, 717, 65, 999, 673, 595, 376, 480, 782, 929, 288, 810, 400, 546, 78, 991, 566, 494, 904, 461, 110, 741, 757, 743, 351, 570, 713, 615, 589, 838, 433, 970, 895, 767, 862, 314, 601, 205, 316, 831, 912, 453, 701, 919, 778, 843, 891, 794, 612, 287, 403, 358, 812, 336, 455, 114, 758, 116, 456, 467, 895, 108, 273, 887, 561, 586, 841, 858, 548, 352, 216, 425, 537, 990, 305, 568, 138, 985, 274, 436, 483, 749, 693, 817, 789, 325, 667, 481, 723, 725, 742, 420, 851, 666, 849, 893, 169, 911, 320, 696, 241, 108, 633, 877, 343, 898, 690, 986, 721, 819, 160, 238, 780, 185, 143, 473, 208, 506, 829, 747, 640, 407, 734, 84, 724, 873, 492, 798, 839, 161, 141, 696, 571, 688, 866, 111, 795, 651, 983, 664, 748, 875, 814, 710, 556, 219, 72, 462, 948, 89, 114, 497, 176, 68, 409, 826, 181, 118, 781, 394, 123, 644, 149, 665, 739, 381, 912, 256, 693, 752, 810, 697, 50, 739, 315, 219, 930, 411, 453, 362, 845, 609, 485, 461, 920, 290, 815, 283, 778, 635, 787, 154, 987, 404, 60, 414, 462, 919, 864, 356, 124, 169, 133, 586, 242, 302, 428, 68, 517, 576, 300, 432, 203, 228, 932, 657, 916, 997, 852, 197, 625, 157, 603, 475, 937, 215, 710, 234, 645, 281, 569, 645, 912, 390, 361, 853, 661, 981, 290, 303, 303, 342, 215, 716, 136, 293, 579, 555, 197, 299, 969, 619, 279, 696, 820, 374, 748, 521, 788, 482, 538, 896, 600, 574, 189, 318, 857, 125, 752, 190, 104, 987, 617, 531, 929, 602, 423, 242, 328, 461, 780, 409, 474, 903, 675, 388, 625, 80, 230, 500, 653, 546, 990, 138, 576, 888, 481, 402, 487, 948, 226, 441, 431, 145, 765, 222, 933, 276, 182, 769, 228, 91, 935, 728, 385, 543, 466, 415, 574, 227, 319, 572, 752, 759, 239, 724, 956, 709, 861, 512, 157, 294, 950, 265, 741, 373, 498, 767, 1000, 957, 168, 149, 668, 811, 573, 658, 971, 711, 662, 352, 473, 404, 868, 750, 793, 614, 532, 853, 620, 918, 283, 301, 547, 221, 486, 164, 664, 275, 287, 360, 79, 680, 59, 461, 874, 283, 438, 512, 358, 378, 559, 378, 681, 841, 479, 454, 513, 419, 310] back = [2, 3, 5, 7] s = Solution() print(s.backPack4(9000,nums))