第5次数据结构上机(01背包递归求解)

xiaoxiao2021-02-28  6

实验名称:用递归算法解决实际问题

指导教师:           王莹洁              

专业班级:       计163-1        

姓   名:      曹欣宇              

学   号:      201658503125             

一、实验题目

编写一个程序exp5-2.cpp,求解背包问题:设有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的方案,使选中物品的总重量不超过指定的限制重量,但选中物品的总价值最大。

二、实验目的

灵活运用递归算法解决一些较复杂应用问题。

三、实验步骤

(包括基本设计思路、算法设计、函数相关说明、输入与输出以及程序运行结果)

基本设计思路:递归。

算法设计:

递归公式:bag(n,c)=max{bag(n-1,c), bag(n-1,c-w[n])+v[n]},其中,n为物品个数,c为背包最大容纳量,w[]为每个物品的重量,v[]为每个物品的价值。

具体算法:

设置一个判断数组ju[],规定值为1则为选中,值为0则为没选中,进入递归后,若n或m等于零,则最优解为0;若物品值大于c,则相当于物品数量减1,即返回bag(n-1,c),并且ju[]赋值为0,否则根据递归公式,比较两公式的值,决定进行哪一步递归,其中,若执行bag(n-1,c-w[n])+v[n]公式,表示已选中该物品,n的数量减1,容纳重量减去该物品的重量,总价值加上物品的价值,并且ju[]赋值为1,反之,若执行bag(n-1,c),表示没有选中,n数量减1。最后,主函数中,bag函数的返回值即为最大价值,然后根据ju[]数组值来确定选取了哪些物品。

函数相关说明:int bag(int n,int c)//进行递归调用

输入:5

          10,100

          8,90

          9,120

          12,150

          6,80

          20

输出:见运行图。

运行结果:

五、实验心得体会

通过这次实验,我更加深刻理解了递归,递归不需要纠结于具体的问题解决的路子,只需要注重在问题大化小之后的情况就好。

 

六、源程序清单(代码)

#include <stdio.h> #include <stdlib.h> int w[50],v[50]; int ju[50]; int bag(int n,int c) { if (n==0||c==0) return 0; else { if ((c>=w[n])&&(bag(n-1,c)<(bag(n-1,c-w[n])+v[n]))) { ju[n]=1; return bag(n-1,c-w[n])+v[n]; } else { ju[n]=0; return bag(n-1,c); } } } int main() { int n,i,j; int c; int max_v; printf("物品总数:\n"); scanf("%d",&n); for(j=1; j<=n; j++) { printf("第%d种物品(重量,价值):",j); scanf("%d,%d",&w[j],&v[j]); } printf("背包所能承受的总重量为:"); scanf("%d",&c); printf("最佳填装方案:\n"); max_v=bag(n,c); for(i=1; i<=n; i++) { if(ju[i]==1) printf("第%d种物品\n",i); } printf("总价值:%d",max_v); return 0; }

转载请注明原文地址: https://www.6miu.com/read-1100339.html

最新回复(0)