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

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

指导教师：           王莹洁              

专业班级：       计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;
}

最后

以上就是俊逸心情为你收集整理的第5次数据结构上机（01背包递归求解）的全部内容，希望文章能够帮你解决第5次数据结构上机（01背包递归求解）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。