01背包问题（一）

无道

发布于 2019-11-13 15:55:32

3640

发布于 2019-11-13 15:55:32

文章被收录于专栏：无道编程无道编程

链接：https://www.acwing.com/problem/content/2/

参考

思路

根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现；

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

过程

把背包问题抽象化，每件物品我们可以选、不选，两种情况。怎么确定选与不选？在此问题中，判断选了的当前物品选了的价值大，还是不选的价值大。

但上面所说的有前提：背包能装下当前的物品。装不下一切免谈。

所以情况如下：（j表示当前背包容量，V(i,j)是当前背包容量 j，前 i 个物品最佳组合对应的价值；）

背包容量小于当前物品价值，那么当前价值 = 上一件物品价值。即： j<w(i) V(i,j)=V(i-1,j)
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个即：j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

代码

#include <iostream>

using namespace std;

int main() {
    int N, V;
    int v[1001] = {0}, w[1001] = {0};
    // v物品体积，w物品价值
    int value[1001][1001] = {0};
    cin >> N >> V;
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= N; ++i) { // i循环物品数量
        for (int j = 1; j <= V; ++j) { // j循环背包容量
            if (j < v[i]) {
                value[i][j] = value[i - 1][j];
            } else {
                value[i][j] = max(value[i - 1][j], value[i - 1][j - v[i]] + w[i]);
                //    其中V(i-1,j)表示不装，
                //    V(i-1,j-v(i))+w(i) 表示装了第i个商品，背包容量减少v(i)但价值增加了w(i)；
            }
        }
    }
    int res = 0;
    for (int k = 0; k <= V; ++k) {
        res = max(res, value[N][k]);
    }
    cout << res << endl;


    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-06-11，如有侵权请联系 cloudcommunity@tencent.com 删除

https