建议和反馈

请填写你的反馈内容

01背包问题是什么,详细教程

2020-02-13 ·569次阅读 ·读完需要3分钟

在本教程中,我们将学习关于0 1背包问题。在这个动态规划问题中,我们有n个项目,每个项目都有相关的权重和价值(收益或利润)。目的是在背包中装满物品,以使我们获得最大的利润,而不会超过背包的重量限制。由于这是一个0 1背包问题,因此我们可以拿走整个物品,也可以完全拒绝。我们不能破坏物品并装满背包。

记住点


  • 在这个问题中,我们有一个重量限制为W的背包。

  • 有项i1,i2,...,每个项的权重分别为w1,w2,…wn和与之相关的收益(价值或利润)v1,v2,... vn

  • 我们的目标是使收益最大化,从而使背包内的总重量最大为W。

  • 由于这是一个0 1背包问题算法,因此我们可以提取整个项目或完全拒绝它。我们不能破坏物品并装满背包。


问题

假设我们有一个最大重量为W = 5 
的背包,我们的目标是在背包中装满物品,以使收益(价值或利润)最大。

下表包含了这些物品及其价值和重量。

项目我1个234
价值价值100206040
重量wt3241个

项目总数n = 4 
背包的总容量W = 5

现在我们创建一个值表V [i,w],其中,i表示项目数,w表示项目的权重。
行表示项目,列表示重量。
因为有4个项目,所以从0到4有5行。
背包的重量限制为W = 5,所以从0到5有6列

V [i,w]w = 01个2345
我= 0





1个





2





3





4





我们用0填充第一行i =0。这意味着当0项被认为重量为0时。

然后,我们用0填充第一列w =0。这意味着当权重为0时,则考虑的项为0。

填写V [i,w]表的规则。

if wt[i] > w thenV[i,w] = V[i-1,w]else if wt[i] <= w thenV[i,w] = max( V[i-1,w], val[i] + V[i-1, w - wt[i]] )


计算后,值表V

V [i,w]w = 01个2345
我= 0000000
1个000100100100
20020100100120
30020100100120
404040100140140

赢得的
最大值最大值= V [n,W] 
= V [4,5] 
= 140

Items that were put inside the knapsackare found using the following ruleset i = n and w = Wwhile i and w > 0 do
  if V[i,w] != V[i-1,w] then
    mark the ith item
    set w = w - wt[i]
    set i = i - 1
  else
    set i = i - 1
  endifendwhile

因此,我们放入背包的物品是4和1。

C代码

#includevoid knapSack(int W, int n, int val[], int wt[]);int getMax(int x, int y);int main(void) {
  //the first element is set to -1 as
  //we are storing item from index 1
  //in val[] and wt[] array
  int val[] = {-1, 100, 20, 60, 40};  //value of the items
  int wt[] = {-1, 3, 2, 4, 1};        //weight of the items
  
  int n = 4;  //total items
  int W = 5;  //capacity of knapsack
  
  knapSack(W, n, val, wt);
  return 0;}int getMax(int x, int y) {
  if(x > y) {
    return x;
  } else {
    return y;
  }}void knapSack(int W, int n, int val[], int wt[]) {
  int i, w;
  //value table having n+1 rows and W+1 columns
  int V[n+1][W+1];
  //fill the row i=0 with value 0
  for(w = 0; w <= W; w++) {
    V[0][w] = 0;
  }
  //fille the column w=0 with value 0
  for(i = 0; i <= n; i++) {
    V[i][0] = 0;
  }
  //fill the value table
  for(i = 1; i <= n; i++) {
    for(w = 1; w <= W; w++) {
      if(wt[i] <= w) {
        V[i][w] = getMax(V[i-1][w], val[i] + V[i-1][w - wt[i]]);
      } else {
        V[i][w] = V[i-1][w];
      }
    }
  }
  //max value that can be put inside the knapsack
  printf("Max Value: %d\n", V[n][W]);}

时间复杂度

0 1背包问题的时间复杂度为O(nW),其中,n是物品的数量,W是背包的容量。


评论(0)问答(0)
请先登录或注册

请先登陆或注册

相关推荐

区块链开发教程: 使用Javascript发送数据到区块链

Bitpay开源了它们的Bitcore库包,我们可以使用它来基于Node.js发送信息到区块链。该库包能让我们生产比特币交易,却不用花费几天时间下载完整的区块链账本。想象比特币和区块链如同笔和新的页面......
区块链论坛 · 2020-02-21
436阅读 · 0赞赏 · 0问答

如何逐步构建完整的堆栈去中心化应用程序

今天,我将向您展示如何在以太坊区块链上构建第一个去中心化应用程序或dApp。我将向您展示如何编写您的第一个以太坊智能合约,我们将在两个候选人之间进行选举。我们将针对智能合约编写测试,将其部署到以太坊区......
BTC · 2020-02-20
440阅读 · 0赞赏 · 0问答

Sublime设置简单指南

Sublime Text具有许多不同的设置来自定义其行为。可以通过编辑文本文件来更改设置:尽管这比使用GUI稍微复杂一些,但您会获得灵活的系统奖励。设定值可以通过“ 首选项设置”菜单项访问设......
江南烟雨 · 2020-02-19
467阅读 · 0赞赏 · 0问答

区块链操作系统是什么,详细指南

尽管世界各地的高级管理人员正在尝试使用区块链,并且几乎每个人都听说过该术语,但很少有人听说过“区块链操作系统”。然而,就像Windows,Linux和macOS等操作系统已成为集中式操作系统不可或缺的......
区块链网 · 2020-02-19
477阅读 · 0赞赏 · 0问答

对称加密是什么意思?

对称加密是一种加密形式,其中相同的密钥用于加密和解密消息。这与非对称或公共密钥加密不同,后者使用一个密钥对消息进行加密,并使用另一密钥对消息进行解密。对称加密是一种计算机加密技术,它使用特定的加密密钥......
开发者小白 · 2020-02-17
485阅读 · 0赞赏 · 0问答

2280

LK币

21

粉丝

80

笔记

感谢"论坛咸鸟"

这篇精彩的笔记,目前已经帮助

  • 0
  • 0
  • 5
  • 6
  • 9
喜欢0
链客社群 加入

微博进入

商务合作>

广告投放>

公司名称:北京链客行科技有限公司

联系方式:010-67707199

ICP备案号:京ICP备18032136号

Copyright:链客区块链技术问答社区 版权所有

感谢您的提问,问题被社区永久收入以便新人查看。一定要记得采纳最佳答案哦!加油!

感谢您的善举,每一次解答会成为新人的灯塔,回答被采纳后获得20算力和相应的LK币奖励

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!