实验4 “0-1”背包问题

实验四 “0-1”背包问题

一、实验目的

熟悉C/C++语言的集成开发环境；

通过本实验加深对贪心算法、动态规划算法的理解。

二、实验内容

掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题 的求解方法，并分析其优缺点。

三、实验要求

1. “0-1”背包问题的贪心算法

2. “0-1”背包问题的动态规划算法

四、实验步骤

理解算法思想和问题要求；

编程实现题目要求；

上机输入和调试自己所编的程序；

验证分析实验结果；

整理出实验报告。

五、实验程序

#include <stdio.h>

#include "iostream"

using namespace std;

int max(int a,int b)

{

if(a > b)

return a;

else

return b;

}

void ZeroOneBag(int *v,int *w,int *x,int c,int n, int m[8][100])

{

int i,j;

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

{

if (j < w[n]) //从第N件物品开始，如果放不下

m[n][j]=0;

else //如果放的下

m[n][j]=v[n];

}

for(i = n-1; i >= 1; i--) //控制物品的循环,从i-1到第1件

{

for(j = 0; j < w[i]; j++) //贪心法把此行注释

m[i][j]=m[i+1][j]; //贪心法把此行注释

for(j=w[i]; j<=c; j++)

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

}

for(i = 1; i < n; i ++) //构造最优解

{

if(m[i][c] == m[i+1][c])

x[i] = 0;

else

{

x[i] = 1;

c = c-w[i];

}

}

x[n] = (m[n][c])?1:0; //m[n][c]大于0吗？大于就是选了

return;

}

void main()

{

int i=0,n=7;

int w[]={0,2,3,5,7,1,4,1};

int v[]={0,10,5,15,7,6,18,3};

int x[]={0,0,0,0,0,0,0,0};

cout<<"程序自带数据为："<<"\n";

cout<<"编号 重量 价值"<<endl;

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

{

cout<<" "<<i+1<<" "<<w[i+1]<<" "<<v[i+1]<<endl;

}

int m=15;

int array[8][100]={0};

ZeroOneBag(v,w,x,m,7,array);

cout<<"\n背包能装的最大价值为: "<<array[1][m];

cout<<"\n\n最优解为:";

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

cout<<" "<<x[i]<<" ";

cout<<"\n\n";

system("pause");

}

六、实验结果

1.贪心法 2.动态规划法

七、实验分析 解决0/1背包问题的方法有多种，最常用的有贪心法和动态规划法。其中贪心法无法得到问题的最优解，而动态规划法都可以得到最优解。动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪心算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心算法中，每采用一次贪心准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。