当前位置:   article > 正文

【算法】利用动态规划实现0-1背包问题_1、试用动态规划算法实现 0-1 背包问题。(30 分)

1、试用动态规划算法实现 0-1 背包问题。(30 分)

描述

给定一个物品集合s={1,2,3,…,n},物品i的重量是wi,其价值是vi,背包的容量为W,即最大载重量不超过W。在限定的总重量W内,我们如何选择物品,才能使得物品的总价值最大。

分析

如果物品不能被分割,即物品i要么整个地选取,要么不选取;
不能将物品i装入背包多次,也不能只装入部分物品i,则该问题称为0—1背包问题。
如果物品可以拆分,则问题称为背包问题,适合使用贪心算法
在这里插入图片描述
在这里插入图片描述
建立计算p(i,j)的递归式如下:
在这里插入图片描述
在这里插入图片描述
m[2][1]=max(m[3][1],m[3][0]+10)=10;
m[2][2]=max(m[3][2],m[3][1]+10)=15;
m[2][3]=max(m[3][3],m[3][2]+10)=25;
m[2][4]=max(m[3][4],m[3][3]+10)=30;
m[2][5]=max(m[3][5],m[3][4]+10)=35;
m[1][5]=max(m[2][5],m[2][3]+12)=37;

求最优解

在这里插入图片描述

代码

时间复杂度O(nW)

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

#define NUM 50
#define CAP 1500
int v[NUM];
int w[NUM];
int p[NUM][CAP];
void knapsack(int c, int n)
{
    int jMax=min(w[n]-1,c);
    for( int j=0; j<=jMax; j++)
        p[n][j]=0;
    for( int j=w[n]; j<=c; j++)
        p[n][j]=v[n];
    for( int i=n-1; i>1; i--)
    {
        jMax=min(w[i]-1,c);
        for( int j=0; j<=jMax; j++)
            p[i][j]=p[i+1][j];
        for(int j=w[i]; j<=c; j++)
            p[i][j]=max(p[i+1][j], p[i+1][j-w[i]]+v[i]);
    }
    p[1][c]=p[2][c];
    if (c>=w[1])
        p[1][c]=max(p[1][c], p[2][c-w[1]]+v[1]);
}

void traceback( int c, int n, int x[ ])
{
    for(int i=1; i<n; i++)
    {
        if (p[i][c]==p[i+1][c])
            x[i]=0;
        else
        {
            x[i]=1;
            c-=w[i];
        }
    }
    x[n]=(p[n][c])? 1:0;
}

int main ()
{
    int x[NUM];
    int W;
    int n;
    while (cin>>W && W)
    {
        cin>>n;
        for (int i=1; i<=n; i++)
            cin>>w[i]>>v[i];
        memset (p, 0, sizeof(p));
        knapsack(W, n);
        cout<< p[1][W]<<endl;
        traceback(W, n, x);
        for (int i=1; i<=n; i++)
            if (x[i])
                cout<< i;
        cout<<endl;
    }
    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
  • 61
  • 62
  • 63
  • 64
  • 65
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/401525
推荐阅读
相关标签
  

闽ICP备14008679号