1. 动态规划：将问题划分为子问题，并使用动态规划的方式逐步求解。
可以使用一个二维数组来存储子问题的解，最终得到问题的最优解。
2. 回溯法：通过尝试所有可能的解决方案，找到满足条件的解。
这种方法可能会涉及到大量的重复计算和大量的时间复杂度。
3. 贪心算法：按照某种规则或者价值大小进行排序，然后依次选择物品放入背包，直到无法再放入为止。
贪心算法不保证一定能够找到最优解，但是可以在某些情况下得到一个近似的最优解。
4. 分支限界法：通过构造搜索树，列举所有可能的解，然后通过剪枝操作去掉不可能得到最优解的路径，最终找到问题的最优解。
这种方法可以在有规模较大的问题时，避免尝试所有可能的解决方案。