澳门新葡亰娱乐网址 澳门新葡亰官方登录 动态规划之背包问题(01背包,完全背包,多重背包)

动态规划之背包问题(01背包,完全背包,多重背包)



>PLCE背包英国
这款防水背包是“士兵95”款发放装备的组成部分,并被特种部队采用。它具有一个内部合金框架、一条腰带和侧袋。可拆解的侧面小袋可以用来构成一个日常巡逻用的背包,包含一个箍紧的装置。它的颜色为DMP、绿色、黑色。容量为125升。

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

澳门新葡亰官方登录 1

完全背包

问题描述

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

关键思路

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

标签:, , , , , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图