c语言背包问题(动态规划解法)

c语言背包问题(动态规划解法)题目描述:有若干个物品要装进背包,并且每个物品有各自的价值,物品的数量、价值以及背包的容量由用户输入,求背包内能够存入的最大价值为多少,并且求出此时放入了哪些物品输入格式:第一行输入物品的容量r和物品个数n第二行输入每个物品的重量第三行输入每个物品的价值输出格式:第一行输出背包中能够存储的最大价值第二行输出此时背包中的物品编号思路分析:可以把这个问题看成是一个二维数组,行是物品编号,列是背包容量,若物品编号为2,背包容量为4,代表的则是当背包容量为..

大家好,又见面了,我是你们的朋友全栈君。

题目描述:

有若干个物品要装进背包,并且每个物品有各自的价值,物品的数量、价值以及背包的容量由用户输入,求背包内能够存入的最大价值为多少,并且求出此时放入了哪些物品

输入格式:

第一行输入物品的容量r和物品个数n

第二行输入每个物品的重量

第三行输入每个物品的价值

输出格式:

第一行输出背包中能够存储的最大价值

第二行输出此时背包中的物品编号

思路分析: 

  可以把这个问题看成是一个二维数组,行是物品编号,列是背包容量,若物品编号为2,背包容量为4,代表的则是当背包容量为4的时候,前两个物品的最大价值。因此当行为物品数,列为背包容量时,即容量为n的背包能够存储的最大价值。

  因此我们定义一个函数给全局变量二维数组赋值,返回二维数组右下角的值即可。

  那么怎么判断放入了哪些物品呢,此时可以根据算法来逆推,若当前物品在当前容量时的价值,与前一个物品在相同容量时的价值相等,则证明当前物品没有被放进背包。若不相等,则证明当前物品放进了背包,此时物品数-1,容量数减去当前物品的重量。

  因此,我们再定义一个函数来寻找背包内放入了哪些物品,并且还要定义一个全局数组,数组的长度就是物品数,数组里面默认都是0,如果在函数中判断放入了该物品,则物品编号对应的值赋1,最后在主函数中判断即可。,

样例输入:

10 3
3 4 5
4 5 6

样例输出: 

11
2 3

代码实现: 

#include<stdio.h>
int f[100][100];//构建最优矩阵,定义全局变量,默认赋0
int find[100];//定义一个数组,寻找背包内放入了哪些物品

int best(int r,int n,int *weight,int *value)//定义一个构建最优矩阵的函数
{     int i,j;

      for(i=0;i<=n;i++)
        f[i][0]=0;

        for(i=0;i<=r;i++)
        f[0][i]=0;

        for(i=1;i<=n;i++)
          for(j=1;j<=r;j++)
            {   if(weight[i]<=j&&f[i-1][j-weight[i]]+value[i]>f[i-1][j])
                   f[i][j]=f[i-1][j-weight[i]]+value[i];
                 else
                 f[i][j]=f[i-1][j];
            }
            return f[n][r];

}

void object(int r,int n,int *weight)//定义一个函数寻找背包里面放入了哪些物品,因为改变的是全局变量find数组的值,所以函数可以不必有返回值
{        int i,j=r;
        for(i=n;i>=1;i--)
          {   if(f[i][j]!=f[i-1][j])  //如果当前价值,比不放当前物品的价值不一样,则代表放入了当前物品
                {find[i]=1;j=j-weight[i];}
          }
}

int main()
{  int weight[100]={0};
   int value[100]={0};
   int r,n,i,maxvalue;//r为背包容量 n为物品数量 maxvalue为最大的背包价值
   scanf("%d%d",&r,&n);

   for(i=1;i<=n;i++)
     scanf("%d",&weight[i]);//输入物品的重量

    for(i=1;i<=n;i++)
      scanf("%d",&value[i]);//输入物品的价值

      maxvalue=best(r,n,weight,value);

    object(r,n,weight);

    printf("背包的最大价值为:%d\n",maxvalue);

    printf("背包里面存入了物品:");

   for(i=1;i<=n;i++)
     if(find[i]==1)printf("%d ",i);

     return 0;

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159097.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号