（C语言贪心算法）0/1背包问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了（C语言贪心算法）0/1背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Description

已知一个载重为M的背包和n件物品，物品编号从0到n-1。第i件物品的重量为 wi，若将第i种物品装入背包将获益pi，这里，wi>0，pi>0，0<=i<n。所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。

Input

第 1 行中有 2 个正整数 n（n<=50）和M ，表示有 n件物品，背包载重为M(m<=100)。然后输入n个物品的重量，最后输入n个物品的收益值。

Output

最佳装载方案的总收益

Sample Input

3 6

2 3 4

1 2 4

Sample Output

方法：将规模大的问题转化为小问题。

过程：从第一个开始选，选出最优解，依次类推，求出第n个相应的最优解。

#include<stdio.h>

int max(int a,int b){
       return a>b?a:b;
}
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    int w[n],p[n],f[200000]={0};
    for(i=0;i<n;i++) scanf("%d",&w[i]);
    for(i=0;i<n;i++) scanf("%d",&p[i]);
    
    for(i=0;i<n;i++){
    for(j=m;j>=1;j--){
    if(j>=w[i]) f[j]=max(f[j],f[j-w[i]]+p[i]);
    }
    }
    printf("%d",f[m]);
    return 0;
}

这里，我们举个列子，取n=3,M=3;（此处数据取小一点，便于理解）

每个物体重量分别为1 2 1

每个物体收益分别为3 4 5

f[W]是我们最后要求的答案，先把数组f全赋值为0，代表初始利润是0；

我们以i=0时做第一次循环得出相应结果为（j认为是背包中剩余可装重量)

不难发现，在只对第一个物体进行选择时，不同背包容量都做出了最优选择。

接下来在进行i=1时的第二次循环,结果为：

（C语言贪心算法）0/1背包问题

此处没有f[1]是因为1小于第二个物体重量。

i=2，最后一次循环结果为：（C语言贪心算法）0/1背包问题

程序结束，这个程序是求了不同背包容量时对第1、2........n个物体选择时所求的最优解，既然每一小部分都是最优解。那加起来合为一个整体也一定为最优解，如最后一张图片，当背包容量为3时，最优解为9。当背包容量为2时，最优解为8。当背包容量为3时，最优解为5。但我们只需求背包容量为3时的最优解，所以输出f[3],即f[m].文章来源地址https://www.toymoban.com/news/detail-482628.html

到了这里，关于（C语言贪心算法）0/1背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！