美文网首页iOS精品文章C++&数据结构与算法动态规划
动态规划之背包问题（01背包，完全背包，多重背包）

动态规划之背包问题（01背包，完全背包，多重背包）

作者: cherryleechen | 来源:发表于2017-10-29 19:51 被阅读234次

01背包

问题描述

有N个物品，每个物品的重量为weight[i]，每个物品的价值为value[i]。现在有一个背包，它所能容纳的重量为V，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？

关键思路

每个物品无非是装入背包或者不装入背包，那么就一个一个的物品陆续放入背包中。
通过for(int i = V; i >= 0; i--)逆序保证物品的装入或不装入。

程序实现

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int N;//物品个数 5
    int V;//背包容量 15
    cin >> N >> V;
    int weight[N + 1];// 5 4 7 2 6
    int value[N + 1];// 12 3 10 3 6
    weight[0] = value[0] = 0;
    int maxTotalValue[V + 1]; //maxTotalValue[i]:背包已装容量为i时,背包里所装物品的最大总价值
    memset(maxTotalValue, 0, sizeof(maxTotalValue));
    for(int i = 1; i <= N; i++)
        cin >> weight[i] >> value[i];
    for(int j = 1; j <= N; j++)
        for(int i = V; i >= 0; i--)
            {
                cout << "背包已装容量:" << i << endl;
                if(i >= weight[j])
                    {
                        if(maxTotalValue[i] >= value[j] + maxTotalValue[i - weight[j]])
                            //cout << "背包中未装入物品:" << j << endl;
                            ;
                        else
                            {
                                maxTotalValue[i] = maxTotalValue[i - weight[j]] + value[j];
                                cout << "背包中已装入物品:" << j << endl;
                            }
                    }
                else
                    //cout << "背包中未装入物品:" << j << endl;
                    ;


            }
    cout << "背包能装物品的最大总价值:" << maxTotalValue[V] << endl;
    return 0;
}

运行结果及分析

5 15
5 12
4 3
7 10
2 3
6 6
背包已装容量:15
背包中已装入物品:1
背包已装容量:14
背包中已装入物品:1
背包已装容量:13
背包中已装入物品:1
背包已装容量:12
背包中已装入物品:1
背包已装容量:11
背包中已装入物品:1
背包已装容量:10
背包中已装入物品:1
背包已装容量:9
背包中已装入物品:1
背包已装容量:8
背包中已装入物品:1
背包已装容量:7
背包中已装入物品:1
背包已装容量:6
背包中已装入物品:1
背包已装容量:5
背包中已装入物品:1
背包已装容量:4
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包中已装入物品:2
背包已装容量:14
背包中已装入物品:2
背包已装容量:13
背包中已装入物品:2
背包已装容量:12
背包中已装入物品:2
背包已装容量:11
背包中已装入物品:2
背包已装容量:10
背包中已装入物品:2
背包已装容量:9
背包中已装入物品:2
背包已装容量:8
背包已装容量:7
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包中已装入物品:2
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包中已装入物品:3
背包已装容量:14
背包中已装入物品:3
背包已装容量:13
背包中已装入物品:3
背包已装容量:12
背包中已装入物品:3
背包已装容量:11
背包已装容量:10
背包已装容量:9
背包已装容量:8
背包已装容量:7
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包中已装入物品:4
背包已装容量:14
背包中已装入物品:4
背包已装容量:13
背包已装容量:12
背包已装容量:11
背包中已装入物品:4
背包已装容量:10
背包已装容量:9
背包已装容量:8
背包中已装入物品:4
背包已装容量:7
背包中已装入物品:4
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包已装容量:3
背包中已装入物品:4
背包已装容量:2
背包中已装入物品:4
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包已装容量:14
背包已装容量:13
背包已装容量:12
背包已装容量:11
背包已装容量:10
背包已装容量:9
背包已装容量:8
背包已装容量:7
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包能装物品的最大总价值:25


完全背包

问题描述

有N个物品，每种物品有无限个，每个物品的重量为weight[i]，每个物品的价值为value[i]。现在有一个背包，它所能容纳的重量为V，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？

关键思路

通过for(int i = 0; i <= V; i++)顺序保证物品的装入次数不限。

程序实现

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int N;//物品个数 5
    int V;//背包容量 15
    cin >> N >> V;
    int weight[N + 1];// 5 4 7 2 6
    int value[N + 1];// 12 3 10 3 6
    weight[0] = value[0] = 0;
    int maxTotalValue[V + 1]; //maxTotalValue[i]:背包已装容量为i时,背包里所装物品的最大总价值
    memset(maxTotalValue, 0, sizeof(maxTotalValue));
    for(int i = 1; i <= N; i++)
        cin >> weight[i] >> value[i];
    for(int j = 1; j <= N; j++)
        for(int i = 0; i <= V; i++)
            {
                cout << "背包已装容量:" << i << endl;
                if(i >= weight[j])
                    {
                        if(maxTotalValue[i] >= value[j] + maxTotalValue[i - weight[j]])
                            //cout << "背包中未装入物品:" << j << endl;
                            ;
                        else
                            {
                                maxTotalValue[i] = maxTotalValue[i - weight[j]] + value[j];
                                cout << "背包中已装入物品:" << j << endl;
                            }
                    }
                else
                    //cout << "背包中未装入物品:" << j << endl;
                    ;
            }
    cout << "背包能装物品的最大总价值:" << maxTotalValue[V] << endl;
    return 0;
}

运行结果及分析

5 15
5 12
4 3
7 10
2 3
6 6
背包已装容量:0
背包已装容量:1
背包已装容量:2
背包已装容量:3
背包已装容量:4
背包已装容量:5
背包中已装入物品:1
背包已装容量:6
背包中已装入物品:1
背包已装容量:7
背包中已装入物品:1
背包已装容量:8
背包中已装入物品:1
背包已装容量:9
背包中已装入物品:1
背包已装容量:10
背包中已装入物品:1
背包已装容量:11
背包中已装入物品:1
背包已装容量:12
背包中已装入物品:1
背包已装容量:13
背包中已装入物品:1
背包已装容量:14
背包中已装入物品:1
背包已装容量:15
背包中已装入物品:1
背包已装容量:0
背包已装容量:1
背包已装容量:2
背包已装容量:3
背包已装容量:4
背包中已装入物品:2
背包已装容量:5
背包已装容量:6
背包已装容量:7
背包已装容量:8
背包已装容量:9
背包中已装入物品:2
背包已装容量:10
背包已装容量:11
背包已装容量:12
背包已装容量:13
背包已装容量:14
背包中已装入物品:2
背包已装容量:15
背包已装容量:0
背包已装容量:1
背包已装容量:2
背包已装容量:3
背包已装容量:4
背包已装容量:5
背包已装容量:6
背包已装容量:7
背包已装容量:8
背包已装容量:9
背包已装容量:10
背包已装容量:11
背包已装容量:12
背包已装容量:13
背包已装容量:14
背包已装容量:15
背包已装容量:0
背包已装容量:1
背包已装容量:2
背包中已装入物品:4
背包已装容量:3
背包中已装入物品:4
背包已装容量:4
背包中已装入物品:4
背包已装容量:5
背包已装容量:6
背包已装容量:7
背包中已装入物品:4
背包已装容量:8
背包中已装入物品:4
背包已装容量:9
背包中已装入物品:4
背包已装容量:10
背包已装容量:11
背包已装容量:12
背包中已装入物品:4
背包已装容量:13
背包中已装入物品:4
背包已装容量:14
背包中已装入物品:4
背包已装容量:15
背包已装容量:0
背包已装容量:1
背包已装容量:2
背包已装容量:3
背包已装容量:4
背包已装容量:5
背包已装容量:6
背包已装容量:7
背包已装容量:8
背包已装容量:9
背包已装容量:10
背包已装容量:11
背包已装容量:12
背包已装容量:13
背包已装容量:14
背包已装容量:15
背包能装物品的最大总价值:36

多重背包

问题描述

有N个物品，每种物品有num[i]个，每个物品的重量为weight[i]，每个物品的价值为value[i]。现在有一个背包，它所能容纳的重量为V，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？

关键思路

通过int counts = min(i / weight[j], num[j]);限制物品的装入次数。

程序实现

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int N;//物品个数 5
    int V;//背包容量 15
    cin >> N >> V;
    int weight[N + 1];// 5 4 7 2 6
    int value[N + 1];// 12 3 10 3 6
    int num[N + 1];// 2 4 1 5 3
    weight[0] = value[0] = num[0] = 0;
    int maxTotalValue[V + 1]; //maxTotalValue[i]:背包已装容量为i时,背包里所装物品的最大总价值
    memset(maxTotalValue, 0, sizeof(maxTotalValue));
    for(int i = 1; i <= N; i++)
        cin >> weight[i] >> value[i] >> num[i];
    for(int j = 1; j <= N; j++)
        for(int i = V; i >= 0; i--)
            {
                cout << "背包已装容量:" << i << endl;
                if(i >= weight[j])
                    {
                        int counts = min(i / weight[j], num[j]);
                        for(int k = 0; k <= counts; k++)
                            {
                                if(maxTotalValue[i] >= k * value[j] + maxTotalValue[i - k * weight[j]])
                                    ;
                                else
                                    {
                                        maxTotalValue[i] = maxTotalValue[i - k * weight[j]] + k * value[j];
                                        cout << "背包中已装入物品:" << j << ",已装入:" << k << "个" << endl;
                                    }

                            }

                    }
                else
                    ;
            }
    cout << "背包能装物品的最大总价值:" << maxTotalValue[V] << endl;
    return 0;
}

运行结果及分析

5 15
5 12 2
4 3 4
7 10 1
2 3 5
6 6 3
背包已装容量:15
背包中已装入物品:1,已装入:1个
背包中已装入物品:1,已装入:2个
背包已装容量:14
背包中已装入物品:1,已装入:1个
背包中已装入物品:1,已装入:2个
背包已装容量:13
背包中已装入物品:1,已装入:1个
背包中已装入物品:1,已装入:2个
背包已装容量:12
背包中已装入物品:1,已装入:1个
背包中已装入物品:1,已装入:2个
背包已装容量:11
背包中已装入物品:1,已装入:1个
背包中已装入物品:1,已装入:2个
背包已装容量:10
背包中已装入物品:1,已装入:1个
背包中已装入物品:1,已装入:2个
背包已装容量:9
背包中已装入物品:1,已装入:1个
背包已装容量:8
背包中已装入物品:1,已装入:1个
背包已装容量:7
背包中已装入物品:1,已装入:1个
背包已装容量:6
背包中已装入物品:1,已装入:1个
背包已装容量:5
背包中已装入物品:1,已装入:1个
背包已装容量:4
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包中已装入物品:2,已装入:1个
背包已装容量:14
背包中已装入物品:2,已装入:1个
背包已装容量:13
背包已装容量:12
背包已装容量:11
背包已装容量:10
背包已装容量:9
背包中已装入物品:2,已装入:1个
背包已装容量:8
背包已装容量:7
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包中已装入物品:2,已装入:1个
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包已装容量:14
背包已装容量:13
背包已装容量:12
背包已装容量:11
背包已装容量:10
背包已装容量:9
背包已装容量:8
背包已装容量:7
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包中已装入物品:4,已装入:2个
背包已装容量:14
背包中已装入物品:4,已装入:2个
背包已装容量:13
背包中已装入物品:4,已装入:1个
背包已装容量:12
背包中已装入物品:4,已装入:1个
背包已装容量:11
背包已装容量:10
背包已装容量:9
背包中已装入物品:4,已装入:2个
背包已装容量:8
背包中已装入物品:4,已装入:1个
背包已装容量:7
背包中已装入物品:4,已装入:1个
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包中已装入物品:4,已装入:2个
背包已装容量:3
背包中已装入物品:4,已装入:1个
背包已装容量:2
背包中已装入物品:4,已装入:1个
背包已装容量:1
背包已装容量:0
背包已装容量:15
背包已装容量:14
背包已装容量:13
背包已装容量:12
背包已装容量:11
背包已装容量:10
背包已装容量:9
背包已装容量:8
背包已装容量:7
背包已装容量:6
背包已装容量:5
背包已装容量:4
背包已装容量:3
背包已装容量:2
背包已装容量:1
背包已装容量:0
背包能装物品的最大总价值:30


相关文章

网友评论

  • fengjb:请问0-1背包问题中的例子，15号背包不是装了1，2，3，4吗，为什么是1，3，4？怎么得到的呢？
    fengjb:@cherryleechen 原来如此，懂了，谢谢，我觉得用代码实现比手工去找更好
    cherryleechen:15是背包的容量。可参考0-1背包问题最后的表，从下往上、从右往左看，4放进去后容量只剩下13，找13对应的那一列发现是放3，放完3后容量还剩6，找6对应的那一列，发现放的是1，所以，最终结果是1、3、4。

本文标题：动态规划之背包问题（01背包，完全背包，多重背包）

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

延伸阅读

深度阅读

  • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

iOS精品文章

C++&数据结构与算法

动态规划

动态规划

关于我们|服务条款|联系我们|动态规划之背包问题（01背包，完全背包，多重背包）|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！