基于c语言的动态规划解决0-1背包问题_01背包问题动态规划算法c语言

• 实验内容

分别用编程实现动态规划算法和贪心法求0-1背包问题的最优解，分析比较两种算法的时间复杂度并验证分析结果

• 问题描述

内容：.给定多种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?

要求：使用动态规划算法编程，求解0-1背包问题

三．算法描述

1、动态规划法

01背包问题的状态转换公式为：

   （1） V(i, 0)= V(0, j)=0

  

  （2）  

公式表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；如果第i个物品的重量小于背包的容量，则会有以下两种情况：

1. 如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；
2. 如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。

 2、贪心法

背包问题至少有三种看似合理的贪心策略：

（1）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。

（2）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。

（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡，即利用性价比求的目标函数最大。

应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。

四．算法实现

动态规划法：

1. 数据结构及函数说明

 int max(int i,int j);//比较并返回两个数中的较大值

 int KnapSack (int w[],int v[],int x[],int n,int c);//求解背包取得的最大值

1. 源程序代码

#include<iostream>

#include "stdio.h"

#include <stdlib.h>

#include<time.h>

using namespace std;

//比较并返回两个数中的较大值

int max(int i,int j)

{

if(i<j)

return j;

else

return i;

}

//求解背包取得的最大值

int KnapSack (int w[],int v[],int x[],int n,int c)

{

int i,j,V[105][1005]={0};

for(i=0;i<=n;i++)//初始化第0列

V[i][0]=0;

for(j=0;j<=c;j++)//初始化第0行

V[0][j]=0;

for(i=1;i<=n;i++)//计算第i行，进行第i次迭代

{

for(j=1;j<=c;j++)

{

if(j<w[i])

V[i][j]=V[i-1][j];

else

V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);

}

}

for(j=c,i=n;i>0;i--)//求装入背包的物品编号

{

if(V[i][j]>V[i-1][j])

{

x[i]=1;

j=j-w[i];

}

else x[i]=0;

}

     return V[n][c];

}

int main()

{

int c,n,w[105],v[105],x[105],max;//x[]记录物品的选择情况

int i,j,k=10;

FILE *fp,*fp1;//定义文件指针

    if((fp=fopen("input.txt","r"))==NULL)//如果文件名不存在

        {cout<<"无法找到文件";}

while(k--){

        clock_t start,finish;

        double totaltime;

        start=clock();

        cout<<"请输入背包的容量：";

            fscanf(fp,"%d",&c);

            cout << c <<"\n";

        cout<<"请输入物品的个数：";

            fscanf(fp,"%d",&n);

            cout << n <<"\n";

        cout<<"请分别输入物品的重量：";

        for(i=1;i<=n;i++){

            fscanf(fp,"%d",&w[i]);

            cout << w[i] <<" ";

            }

        cout<<endl;

    

贪心法：

1. 数据结构及函数说明

struct good//表示物品的结构体

{

     int value;//价值

     int weight;//重量

     double ratio;//价值与重量的比

};

bool bigger(good a,good b);//按比较物品的价值与重量比和质量选择较大的

1. 源程序代码

#include<iostream>

#include<algorithm>

#include "stdio.h"

#include <stdlib.h>

#include<time.h>

using namespace std;

struct good//表示物品的结构体

{

    int value;//价值

    int weight;//重量

    double ratio;//价值与重量的比

};

good a[2000];

bool bigger(good a,good b)

{

    if(a.ratio==b.ratio)return a.weight<b.weight;

    else return a.ratio>b.ratio;

}

int main()

{

    double s,total;

    int c,i,n,k=10;

FILE *fp;//定义文件指针

    if((fp=fopen("input.txt","r"))==NULL)//如果文件名不存在

        {cout<<"无法找到文件";}

while(k--){

    clock_t start,finish;

    double totaltime;

    start=clock();

    cout<<"请输入背包的容量：";

    fscanf(fp,"%d",&c);

    cout << c <<"\n";

    cout<<"请输入物品的个数：";

    fscanf(fp,"%d",&n);

    cout << n <<"\n";

    cout<<"请分别输入物品的重量：";

    for (i=0;i<n;i++)

    {

        fscanf(fp,"%d",&a[i].weight);

        cout << a[i].weight <<" ";

    }

    cout<<endl;

    cout<<"请分别输入物品的价值：";

    for (i=0;i<n;i++)

    {

        fscanf(fp,"%d",&a[i].value);

        cout << a[i].value <<" ";

        a[i].ratio=a[i].value/a[i].weight;

    }

    for (i=0;i<n;i++){

        if(s+a[i].weight<=c)

        {

            cout<<n-i<<" ";

            total+=a[i].value;

            s+=a[i].weight;

        }

    }

五．程序运算结果

1. 动态规划法
2. 

 

六．实验结果分析及结论

整理实验结果可以得到下表比较动态规划法和贪心法：

通过上表，我们可以看出当背包容量不是很大，物品个数不是很多的时候，动态规法和贪心法的时间开销没有太大差距；当容量和物品个数增大时，动态规划法所用的时间增长远大于贪心法。而解的精确度方面，动态规划法得到的解都比贪心法的更加精确。

通过比较动态规划法、贪心法解决0/1问题，可以发现，动态规划法所需的的时间开销迅速增大，用于存放迭代结果的二维数组V[n][n]的计算时间延长，增大了时间开销；贪心法要对输入物品的顺序按照单位价值量递减进行排序的问题，采用不同的排序算法会影响算法的执行速度，为了保证物品的顺序不变，不同的策略也会产生不同的效果；贪心法得到的是局部最优解，不一定能得到整体最优解，动态规划法得到的解更精确。

七．总结

本次实验中使用了c语言来进行编程，中间遇到了不少坎坷，但最终还是克服，此外我认为该算法复杂度还是偏高，有优化空间。