2023年8月1日发(作者：)

01背包问题递归算法c语⾔,递归算法解决01背包问题并输出最佳⽅案问题及代码：/** Copyright (c) 2016, 烟台⼤学计算机与控制⼯程学院* All rights reserved.* ⽂件名称：* 作 者：单昕昕* 完成⽇期：2016年5⽉16⽇* 版 本 号：v1.0* 问题描述：编写⼀个程序，求解背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取⼀部分物品的⽅案，使选中物品的总重量不超过指定的限制重量，但选中物品的总价值最⼤。* 程序输⼊：n种物品的价值和重量。* 程序输出：选取物品的最佳⽅案和物品的最⼤总价值。*/#include#include#includeusing namespace std;#define MAXN 1001int w[MAXN],v[MAXN],vis[MAXN][MAXN];//分别表⽰物品重量、价值和是否取得该⽅案的标记int n;//物品总数int rec(int i,int j,int sum){int res;if(i==n) res=sum;//递归出⼝else if(j{res=rec(i+1,j,sum);vis[i-1][j]=0;}else{if(rec(i+1,j,sum)res=max(rec(i+1,j,sum),rec(i+1,j-w[i],sum+v[i]));}return res;}int main(){memset(w,0,sizeof(w));//初始化memset(v,0,sizeof(v));memset(vis,0,sizeof(vis));cout>n;int i,cnt=0;char c;//逗号的输⼊for(i=0; i{cout>w[i]>>c>>v[i];}cout>vol;cout

2023年8月1日发(作者：)

01背包问题递归算法c语⾔,递归算法解决01背包问题并输出最佳⽅案问题及代码：/** Copyright (c) 2016, 烟台⼤学计算机与控制⼯程学院* All rights reserved.* ⽂件名称：* 作 者：单昕昕* 完成⽇期：2016年5⽉16⽇* 版 本 号：v1.0* 问题描述：编写⼀个程序，求解背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取⼀部分物品的⽅案，使选中物品的总重量不超过指定的限制重量，但选中物品的总价值最⼤。* 程序输⼊：n种物品的价值和重量。* 程序输出：选取物品的最佳⽅案和物品的最⼤总价值。*/#include#include#includeusing namespace std;#define MAXN 1001int w[MAXN],v[MAXN],vis[MAXN][MAXN];//分别表⽰物品重量、价值和是否取得该⽅案的标记int n;//物品总数int rec(int i,int j,int sum){int res;if(i==n) res=sum;//递归出⼝else if(j{res=rec(i+1,j,sum);vis[i-1][j]=0;}else{if(rec(i+1,j,sum)res=max(rec(i+1,j,sum),rec(i+1,j-w[i],sum+v[i]));}return res;}int main(){memset(w,0,sizeof(w));//初始化memset(v,0,sizeof(v));memset(vis,0,sizeof(vis));cout>n;int i,cnt=0;char c;//逗号的输⼊for(i=0; i{cout>w[i]>>c>>v[i];}cout>vol;cout