c语言背包问题(动态规划解法)
2023-06-13 09:12:33 时间
大家好,又见面了,我是你们的朋友全栈君。
题目描述:
有若干个物品要装进背包,并且每个物品有各自的价值,物品的数量、价值以及背包的容量由用户输入,求背包内能够存入的最大价值为多少,并且求出此时放入了哪些物品
输入格式:
第一行输入物品的容量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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/159097.html原文链接:https://javaforall.cn
相关文章
- matlab求解下面的线性规划和整数规划[通俗易懂]
- C语言描述 动态规划 背包问题
- 动态规划之01背包问题(最易理解的讲解)[通俗易懂]
- 最详细动态规划解析——背包问题
- 自我学习规划
- 全局路径规划:图搜索算法介绍4(RRT/RRT*)
- 蓝桥杯 2^k 进制数 (动态规划+大数求和)-------C语言—菜鸟级
- 【说站】python动态规划算法的使用过程
- 75张图带你了解网络设备、网络地址规划、静态路由、实战演练
- 数学建模(7)动态规划以及matlab实现
- 网传8月虾皮规模毁offer,程序员该如何做未来的规划和技术储备?
- 网络规划方案又难又烦?建议收藏本文以备不时之需!
- 动态规划算法
- 用javascript分类刷leetcode3.动态规划(图文视频讲解)_2023-03-15
- 【运筹学】整数规划 ( 相关概念 | 整数规划 | 整数线性规划 | 整数线性规划分类 )
- 腾讯宣布正式养鹅,正在贵州规划建山洞鹅厂
- 自动驾驶决策规划技术详解
- oracle常见故障类别及规划解析
- 【ACM】最长公共子序列 – 动态规划详解编程语言
- 构建高效的Oracle存储规划(oracle存储规划)
- 优化Oracle ASM规划,实现零故障运行(oracle asm规划)