当前位置:   article > 正文

【C/C++】动态规划之0-1背包问题_0/1背包问题(c++/动态规划) 给出背包容量w以及n个重量分别为{w1,w2,…,wn}的物品,

0/1背包问题(c++/动态规划) 给出背包容量w以及n个重量分别为{w1,w2,…,wn}的物品,

问题描述:
现有n件物品和一个容量为c的背包。第i件物品的重量是重量为w[i],价值是v[i]。已知对于一件物品必须选择取(用1表示)或者不取(用0表示),且每件物品只能被取一次(这就是“0-1”的含义)。求放置哪些物品进背包,可使这些物品的重量总和不超过背包容量,且价值总和最大。

求解思路:
假设有6件物品,其重量分别是w={4,2,2,6,5,4},价值分别是v={4,6,3,5,4,6},背包容量为10。我们可以先这样考虑,当背包容量为1时,如何放置物品才能使背包中价值最大;同样当背包容量为2时,如何放置能使背包中价值最大,以此类推,直到背包容量为10。此时我们需要一张价值二维表MaxValue[i][j],其中横坐标i表示物品,纵坐标表示背包容量(1<=j<=10)。

下图是将物品分别放入背包中的过程容量最大价值。第一行是物品1分别在容量大小1-10的最大价值,后一行是在前一行的基础上新增物品后能保存的最大值。
在这里插入图片描述
经过几轮比较后,二位数组最后一个位置即是所有物品中能够保存的最大值。

#include<bits/stdc++.h>
using namespace std;
#define N 11

/*
问题描述:
    现有n件物品和一个容量为c的背包。
    第i件物品的重量是重量为w[i],价值是v[i]。
    已知对于一件物品必须选择取(用1表示)或者不取(用0表示),
    且每件物品只能被取一次(这就是“0-1”的含义)。
    求放置哪些物品进背包,可使这些物品的重量总和不超过背包容量,
    且价值总和最大。
*/

int main()
{
	int n,c,w[N]={4,2,2,6,5,4},v[N]={4,6,3,5,4,6};
    int MaxValue[N][N]={0};    //保存价值总和最大
    c = 10;
    n = 6;
    //scanf("%d %d",&n,&c);
    // for(int i = 1;i<=n;i++)
    // {
    //     scanf("%d %d",&w[i],&v[i]);
    // }

    //初始化表第一行
    for(int k=1;k<=c;k++)
    {
        if(w[0]>k) MaxValue[0][k] = 0;//背包装不下,即为0
        else MaxValue[0][k] = v[0];//背包能够装下,价值为该物品价值
    }
    for(int i = 1;i<n;i++)
    {
        for(int j = 1;j<=c;j++)
        {
            if(w[i]>j) MaxValue[i][j] = MaxValue[i-1][j];//判断是否有空间装下该物品,若空间不够,保存前一个物品在该空间容量时的最大价值
            else
            {//若空间足够大,则该物品价值加上剩余空间的最大价值
                if(MaxValue[i-1][j-w[i]]+v[i]>MaxValue[i-1][j]) 
                    MaxValue[i][j] = MaxValue[i-1][j-w[i]]+v[i];
                else 
                    MaxValue[i][j] = MaxValue[i-1][j];
            }          
        }
        
    }

    for(int i=0;i<n;i++)
    {
        for(int j = 1;j<=c;j++)
        {
            printf("%d\t",MaxValue[i][j]);
        }
        printf("\n");
    }
    printf("\n%d\n",MaxValue[n-1][c]);
    return 0;

}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

给的用例最大价值为16

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/401655
推荐阅读
相关标签
  

闽ICP备14008679号