01 背包，二维数组或动态数组都可以。

动态数组

• 从右往左为 01 背包
• 从左向右为 完全背包

状态定义

• 集合：将n件物品放入空间为M的背包的方案
• 限制：物品范围，背包空间
• 属性：价值
• 条件：最大
• 统计量：价值
• 状态定义：dp[i][j]表示将前i件物品放入大小为j的背包能获得的最大价值