经典背包系列问题

🚀 优质资源分享 🚀

经典背包系列问题

作者：Grey

原文地址：

博客园：经典背包系列问题

CSDN：经典背包系列问题

问题一

题目描述

在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为Ai (每个物品只能选择一次且物品大小均为正整数)

题目链接：LintCode 92 · Backpack
​
暴力递归方法思路

定义递归函数

int p(int rest, int i, int[] arr)

1
2

递归含义表示：从 i 开始到最后，还剩下 rest 容量的情况下，得到的最大值是多少。

递归函数中有两个决策，第一个决策，不要当前位置物品

int p1 = p(rest, i+1, arr);

1
2
3

第二个决策，要当前物品，这个决策下，有一个限制条件，即当前物品大小不超过 rest，

arr[i] + p(rest - arr[i], i + 1, arr)

1
2

暴力解法的完整代码如下

public class Solution {

    public static int backPack(int m, int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        return p(m, 0, arr);
    }

    public static int p(int i, int j, int[] arr) {
        if (j == arr.length) {
            return 0;
        }
        int p1 = p(i, j + 1, arr);
        return i >= arr[j] ? Math.max(arr[j] + p(i - arr[j], j + 1, arr), p1) : p1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

超时

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k3N7K1QV-1667408903069)(https://img2022.cnblogs.com/blog/683