C语言算法之0-1背包问题

水深无声 2022-06-05 04:08 204阅读 0赞

有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 w\[i\]，价值是 p\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，价值总和最大

0-1背包问题，表示的是每个物品只有一件，每件物品不能分割，在不超过背包容量的同时，如何选取物品，使得背包所装的价值最大（背包可以装不满）。

该文为0-1背包二维解法，这篇文章介绍了一维解法：[点击打开链接][Link 1]

核心算法：

int bag(int n,int C,int w[],int v[])
    {
        int i,j;
        for(i=0;i<=n;i++)
            jiazhi[i][0]=0;//无论东西有多少，只要背包容积为0，价值就为0
        for(j=0;j<=C;j++)
            jiazhi[0][j]=0;//无论背包有多大，没有物品，价值也为0
        for(i=1;i<=n;i++)//从第一件物品开始
        {
            for(j=1;j<=C;j++)//j代表当前背包容积
            {
                if(j<w[i])//此时装不下了
                    jiazhi[i][j]=jiazhi[i-1][j];
                else
                    jiazhi[i][j]=max(jiazhi[i-1][j],jiazhi[i-1][j-w[i]]+v[i]);
            }
        }
        return jiazhi[n][C];//返回最大价值
    }

完整代码：

#include<queue>
    #include<math.h>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<algorithm>
    using namespace std;
    int jiazhi[2222][2222];//计算最大价值，数组尽量开大点
    int w[222];//代表物品重量
    int v[222];//代表物品价值
    int max(int a,int b)//选取最大值
    {
        if(a>=b)
            return a;
        else
            return b;
    }
    int bag(int n,int C,int w[],int v[])
    {
        int i,j;
        for(i=0;i<=n;i++)
            jiazhi[i][0]=0;//无论东西有多少，只要背包容积为0，价值就为0
        for(j=0;j<=C;j++)
            jiazhi[0][j]=0;//无论背包有多大，没有物品，价值也为0
        for(i=1;i<=n;i++)//从第一件物品开始
        {
            for(j=1;j<=C;j++)//j代表当前背包容积
            {
                if(j<w[i])//此时装不下了
                    jiazhi[i][j]=jiazhi[i-1][j];
                else
                    jiazhi[i][j]=max(jiazhi[i-1][j],jiazhi[i-1][j-w[i]]+v[i]);
            }
        }
        return jiazhi[n][C];//返回最大价值
    }
    int main()
    {
        int n;//物品数量
        int C;//背包容积
        
        int i,j;
        while(scanf("%d%d",&n,&C)!=EOF)
        {
            for(i=1;i<=n;i++)//输入物品质量
                scanf("%d",&w[i]);
            for(i=1;i<=n;i++)//输入物品价值
                scanf("%d",&v[i]);
            printf("%d\n",bag(n,C,w,v));
        }
    }

[Link 1]: http://blog.csdn.net/lee371042/article/details/78609852