云昴(Mao Yun)

【背包问题】01背包问题

| | 【专业·学习】算法

简介

有N件物品、1个容量为W的背包,第1件物品的重量是weight[i], 价值为value[i]。每个物品只能用一次,求解哪些物品装入背包里物品的价值总和最大?

方法

  1. 确定dp数组和下表的含义。dp[i][j]表示从下标为[0-i]的物品里任意取,放进容量为j的背包中,价值最大的值。
  2. 确定递推公式。dp[i][j] =

致谢

公众号:代码随想录

云昴(Mao Yun)