01背包问题

作者: 猴式智减法 | 来源:发表于2018-01-27 14:22 被阅读0次

有n个重量和价值分别为wi,vi的物品。从这些物体中挑选出总重量不超过W的物品,求所有方案中价值总和的最大值。

1 朴素方法

** 将每个物体是否放入背包进行搜索试一试 **

int n, W;
int w[MAX_N], v[MAX_N];

//从第i个物品选择总重小于j的部分
int res(int i, int j) {
    int res;
    if (i == n) {
        //已经没有剩余物品了
        res = 0;
    } else if (j < w[i]) {
        //无法挑选这个物品
        res = rec(i + 1, j);
    } else {
        //挑选和不挑选的情况都试一下,不选这个选下一个或许v更大
        res = max(rec(i + 1, j), rec(i + 1, j + 1) + v[i]);
    }
    return res;
}

void solve() {
    printf("%d\n", rec(0, W));
}

** 这种方法的搜索深度是n,每一层需要两次分支,最坏需要O($2^n$)的时间。**

2 使用数组记录结果,省略第二次以后的重复计算时间。

int dp[MAX_N + 1][MAX_N + 1]; //记忆化数组

int rec(int i, int j) {
    if (dp[i][j] >= 0) {
        //已经计算过的话直接使用之前的结果
        return dp[i][j];
    }
    int res;
    if (i == n) {
        res = 0;
    } else if (j <w[j]) {
        res = rec(i + 1, k);
    } else {
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
    }
    //将结果记入dp数组
    return dp[i][j] = res;
}

void solve() {
    //用-1表示尚未计算过,初始化整个数组
    memset(dp, -1, sizeof(dp));
    printf("%d\n", rec(0, w));
}

** 根据定义,有如下的递推式 **
dp[n][j] = 0;
dp[i][j] = dp[i + 1][j] (j < w[i])
else = max(dp[i + 1][j], dp[i + 1][j -w[i]]+v[i])

int dp[MAX_N + 1][MAX_N + 1]; //记忆化数组

void solve() {
    for (int i = n - 1; i >= 0; i --) {
        for (int j = 0; i < j<= W; ++j) {
            if (j < w[i]) {
                dp[i][j] = dp[i + 1][j];
            } else {
                dp [i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
        
    }
    printf("%d\n", dp[0][W]);
}

** 上面所述的dp中i的循环是逆向进行的,如果按照下面定义递推,则可以正向进行i的循环 **
dp[i + 1][j] :=从0到i这i+1个物品中选出来总重量不超过j的物品时总价值的最大值
dp [0][j] = 0;

dp[i + 1][j] = dp [i][j] (j < w[i])
else = max(dp[i][j], dp[i][j - w[i]] + v[i])

void solve() {
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if (j < w[i]) 
            {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
            }
        }
    }
    printf("%d\n", dp[n][w]);
}

** 还可以把状态转移想象成从"前i个物品中选取总重不超过j时的状态"向"前i + 1个物品中选取总重不超过j"和"前i+1个物品中选取总重不超过j+w[i]时的状态"的转移,于是可以实现下面形式 **

void solve() {
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            dp[i + 1][j] = max(dp[i+1][j], dp[i][j]);
            if (j + w[i] <= W) 
            {
                dp[i + 1]{j + w[i] = max(dp[i + 1][j + w[i], dp[i][j] + v [i]); 
            }
        }
    }
    printf("%d\n", dp[n][w]);
}

相关文章

  • 动态规划-背包问题

    01背包问题 详解:01背包问题详解链接

  • 背包问题1(01背包)

    N件物品,没见有重量Wi,价值Vi;选其中几件放入容量为M的背包中,求价值的最值。——经典背包问题背包问题分三类:...

  • 01背包问题

    动态规划算法一般用来求解最优化问题,当问题有很多可行解,而题目要求寻找这些解当中的“最大值”/“最小值”时,通常可...

  • 01背包问题

    题目描述:给定 n 个物品和一个容量为 W 的背包,物品 i 的重量是 wi,其价值为 vi 。应该如何选择装入背...

  • 01背包问题

    有n个重量和价值分别为wi,vi的物品。从这些物体中挑选出总重量不超过W的物品,求所有方案中价值总和的最大值。 1...

  • 01背包问题

    A - Bone Collector Many years ago , in Teddy’s hometown t...

  • 01背包问题

    令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值,则...

  • 01背包问题

    题目:有A(2kg,6$);B(2kg,3$);C(6kg,5$);D(5kg,4$);E(4kg,6$)五种物品...

  • 01背包问题

    题目: 有限个数的货物,具有不同的体积还有价值,怎么让其放进有限体积的背包并价值最大。 货物只有两种可能,放进去/...

  • 背包01问题

    背包01问题 背包01问题是一个经典的算法。 问题是这样描述的:一个背包最大容量为9kg,现在有5个物品,每个物品...

网友评论

    本文标题:01背包问题

    本文链接:https://www.haomeiwen.com/subject/yzfnaxtx.html