• 实验内容

分别用编程实现动态规划算法和贪心法求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. 

 

六．实验结果分析及结论

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

	1	2	3	4	5	6	7	8	9	10
背包容量	10	15	300	500	800	1000	1000	1000	1000	1000
物品个数	5	7	50	50	80	80	100	100	100	100
最大价值
动态规划	15	54	1063	1162	1989	2104	2647	2315	2533	2151
贪心	15	52	1011	1114	1887	2086	2579	2259	2438	2101
所用时间
动态规划	0.01	0.008	0.04	0.076	0.105	0.121	0.148	0.119	0.124	0.126
贪心	0.011	0.006	0.025	0.051	0.102	0.083	0.126	0.072	0.079	0.153

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

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

七．总结

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