LeetCode-Notes
  • Introduction
  • Records of Practice
  • 关于Github 不支持密码问题
  • 面试题
    • 搜索广告
    • 多模态大模型
    • 刷题记录
  • 算法代码实现
  • Python
    • Python 笔记
  • Spark
    • PySpark
    • Spark Issues
    • Spark调优笔记
  • FeatureEngineering
    • Feature Cleaning
    • Feature Selection
    • Feature Transformation
    • Feature Crossing
  • Recommendation Algorithm
    • Recall-and-PreRank
      • Non-Negative Matrix Fatorization(NMF)
      • Fatorization Machine(FM)
      • User-base/Item-base实现
      • 多路召回实现
    • Ranking
      • NeuralFM
      • DeepFM
      • Deep&Cross network (DCN)
    • DeepLearning-Basic
      • Attention
      • Dropout
      • Batch Norm
  • Machine Learning
    • XGBoost
    • Cross Entropy Loss
    • Other models
  • Graph Neural Network
    • GNN-1-Basic
  • Big Data
    • Reservoir Sampling
  • SQL
    • SQL and PySpark functions
    • Query Film Infomation
    • Create, Insert and Alter Actor Table
    • Manage Employment Data
    • Manage Employment Data -2
  • DataStructure
    • Searching
      • Find power
      • 2 Sum All Pair II
      • Two Sum
      • Search in Rotate Array
      • Search In Shifted Sorted Array II
      • Search in 2D array
      • Three Sum with duplicated values
      • Median of Two Sorted Arrays
    • Array
      • Longest Consecutive Subarray
      • Merge Two Array in-place
      • Trapping water
      • Rotate matrix
    • Sorting
      • Merge intervals
      • 排序
      • 最小的k个数
      • Find TopK largest- QuickSelect快速选择 method
      • MergeSort Linkedlist
      • 第K大元素
    • LinkedList
      • Reverse LinkedList I
      • Reverse K-group linked list
      • Detect Start of Cycle
      • HasCycle
      • DetectCycle II
      • 链表的共同节点
      • 链表中倒数第k个节点
      • 删除链表倒数第k个节点
      • 合并两个链表
      • 在排序数组中查找元素的第一个和最后一个位置
      • 删除链表里面重复的元素-1
    • Tree
      • Find Tree height (general iteration method)
      • Check BST and Check CompleteTree
      • ZigZag Order traversal
      • Binary Tree diameter I
      • Maximum Path Sum Binary Tree
      • Maximum Path Sum Binary Tree II
      • Binary Tree Path Sum To Target III
      • Tree diameter 树的直径II
      • Tree ReConstruction
      • Check if B is Subtree of A
      • The Kth smallest in Binary Search Tree
      • 打印Tree的右视图
      • 二叉搜索树的后序遍历序列
      • 重建二叉树
      • 判断二叉树是否对称
      • Path Sum to Target in Binary Tree
      • Tree-PreOrder-InOrder-PostOrder
    • Heap&Queue
      • Top-K smallest
      • 滑动窗口最大值
      • Find the K-Largest
    • 合并k个已排序的链表
    • String
      • Reverse String
      • 最长不含重复字符的子字符串
      • 最长回文串
      • 最长回文子序列-DP
    • DFS/BFS
      • Number of island
      • Number of Provinces
      • All Permutations of Subsets without duplication
      • All Permutations of Subsets with duplication
      • Combinations Of Coins
      • All Subset I (without fixing size of subset, without order, without duplication)
      • All Subset of K size without duplication II
      • All Subset of K size III (with duplication without considering order)
      • All Permutation II (with duplication and consider order)
      • Factor Combination-质数分解
    • DynamicProgramming
      • DP-解题过程
      • Find Continuous Sequence Sum to Target
      • 1800. Maximum Ascending Subarray Sum
      • NC91 最长上升子序列
      • 查找string的编码方式个数
      • Maximum Product
      • Longest Common Substring
      • Longest Common Substring-II
      • minEditCost
      • Backpack I
      • Array Hopper I
      • Minimum distance between strings
      • 最大正方形
  • Big Data Algorithms
    • Big Data Processing Algorithms
      • Reservior Sampling
      • Shuffle
      • MapReduce
      • Bloom Filter
      • BitMap
      • Heap For Big Data
Powered by GitBook
On this page
  • 1. Link
  • 2. 题目描述
  • 输入
  • 返回值
  • 说明
  • 3. 思路
  • 4. Coding

Was this helpful?

  1. DataStructure
  2. DynamicProgramming

Backpack I

PreviousminEditCostNextArray Hopper I

Last updated 4 years ago

Was this helpful?

1. Link

2. 题目描述

已知一个背包最多能容纳物体的体积为V现有n个物品第i个物品的体积为v_ivi​ 第i个物品的重量为w_iwi​求当前背包最多能装多大重量的物品示例1

输入

复制

10,2,[[1,3],[10,4]]

返回值

复制

4

说明

第一个物品的体积为1,重量为3,第二个物品的体积为10,重量为4。只取第二个物品可以达到最优方案,取物重量为4

3. 思路

  1. 2D - dp: dp table: row = item的id, column =考虑第i个物品后(可以选也可以不选) 剩下volume, dp[i][j] = 在考虑第i个物品 时剩下volume = j情况的的最大重量

  2. 遍历 n items 和 遍历 V volume values, start from j=V and end at j=0

  3. 当j < item的volume, 那么就不用考虑第i个item,于是dp[i][j] = dp[i-1][j] 从上个item的最大值延伸到现在第i个item的状态

  4. 如果j > item的volume, dp[i][j] = max(在第i-1个item的volume=j的情况不加第i个item的最大值,以及在dp[i-1][j-v] +w 上一个item的加上当前第i个item的最大值 )

  5. Time: O(n^2) Space: O(n^2)

  6. Example

4. Coding

class Solution:
    def knapsack(self , V , n , vw ):
        #
        #idea: 2D-DP
        # state in dp[i]: 第i个物品的weight
        # dp[0] = 第一个item weight. if v[0] <= V, dp[0]= w[0] else 0
        # dp[1] 第二个item考虑要不要加上去,  如果v[1] < V,  
        # dp[1] = max(w[1], dp[i-1])
        # 如果 v[i] + v[0] cumulative volume < V:
        # dp[1] = max(w[1], dp[i-1],w[1] + dp[i-1] )
        # update weight and cumulative volume
        #
        #由于 item的组合先后是没有顺序的,对于同一件物品
        # 对应很多种不同的剩余的Volume的情况,所以要2D dp进行组合
        #dp[i][j] 表示 在面对第 i 件物品,且背包剩余容量为 j 时所能获得的最大价值
        # 这里的最大值的剩余容量是包括第i间物品之后的剩余容量
        #     volume  1   2
        # item w
        #   w=1       1    1
        #   w=2       0   2
        #
        if n ==0:
            return 0
        dp = [[0 for i in range(V+1)]]*(n+1)
        for i in range(1,n+1):
            # 从剩余量大的一段开始堆放物品
            for j in range(V,-1,-1):
                v = vw[i-1][0]
                w = vw[i-1][1]
                if v <= j:
                    # 对比没有加上 第i件物品的最大重量和 加上第i件物品的最大重量
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-v]+w )
                else:
                    # 因为放不下第i个物品,所以当前最大值等于第i-1个物品时最大值
                    dp[i][j]= dp[i-1][j]
        return dp[n][V]
        

Logo01背包_牛客题霸_牛客网