2 qq 22584569 qq_22584569 于 2016.04.08 12:57 提问

背包问题算法流程图及时间复杂度 5C

#include "iostream"
#include "vector"

#include "cstring"

using namespace std;

class PackEnum

{

protected:  
vector<int> m_p;  
vector<int> m_w;   
int m_c;  
int m_num;  

public:

PackEnum();

PackEnum(vector& p,vector& w, int c,int n)

:m_p(p),m_w(w),m_c(c),m_num(n)

{}

void GetBestValue();
void init(vector& p);

};

void PackEnum::init(vector& p)
{
int i;
for(i=0;i p[i]=p.size()-i;
}
inline void PackEnum::GetBestValue ()
{
int bestValue=0;
int currentValue =0;
int currentWeight =0;
int MaxWeight=0;
vector a(m_num);

init(a);
unsigned int i;
unsigned int bit1;;
unsigned int Fbit;
const unsigned int max = 2 << m_num;

for( i =0; i {
currentValue =0;
currentWeight =0;
unsigned int bit = i;
bit1=bit;
int j =0;
while(bit !=0)
{
currentWeight += m_w[j] * (bit & 1);
currentValue += m_p[j] * (bit & 1);
bit >>=1;

++j;

}

if(currentWeight <=m_c && bestValue < currentValue)

{

bestValue = currentValue;

MaxWeight = currentWeight;
Fbit = bit1;
}

}

cout<<"背包最大载重为:"< cout for(i=a.size()-1;i>=0;i--)
{
if((Fbit & 1 )!=0)
cout< Fbit >>=1;
}
cout<<endl;

}

int main()

{

int n;

int m;
int i;
cout<<"请输入商品个数:";
cin >>n;
cout<<"请输入背包承受的最大质量:";
cin >>m;
vector w(n);

vector p(n);

for( i=0;i {
cin >> w[i];
cin >> p[i];
}
PackEnum pack(p,w,m,n);

pack.GetBestValue();
return 0;

}

这是算法,求大神做一下流程图和时间复杂度。谢大神!

2个回答

CSDNXIAOD
CSDNXIAOD   2016.04.08 13:02

算法的时间复杂度
算法之时间复杂度和空间复杂度
常用算法和时间复杂度(php)
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

lbcab
lbcab   2016.04.08 14:23

吐槽一下, 你这代码是怎么上传的? 不完整呀......

关于经典的背包问题, 有一个转移方程: f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。
Pi表示第i件物品的价值.
由转移方程来看, 是把背包的承重从0开始到最大承重去分析你所要去填充的物品的最大价值,
下一步的结果依赖于上一步的结果, 背包问题是动态规划类的问题.
算法的时间复杂度是: O(m * n) , m是物品的个数, n是背包的最大承重.
假如: 有a, b, c, d, e五件物品, 重量为2,2,6,5,4, 价值6,3,5,4,6, 有一个承重为10的背包, 那么:

name weight value 1 2 3 4 5 6 7 8 9 10 (这一行代表背包承重)
a 2 6 0 6 6 9 9 12 12 15 15 15
b 2 3 0 3 3 6 6 9 9 9 10 11
c 6 5 0 0 0 6 6 6 6 6 10 11
d 5 4 0 0 0 6 6 6 6 6 10 10
e 4 6 0 0 0 6 6 6 6 6 6 6

此图(.....)从下往上从左往右看,(按照转移方程看) 当只有e物品,最大价值为6, 当有e, d 物品最大价值10, .....所以a, b, c, d, e, 背包最大价值为15.
应该够详细了.....

lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 你既然问了程序问题你应该是搞it的, 复杂度和分析程序还是自己学习了解的比较好
一年多之前 回复
lbcab
lbcab 回复qq_22584569: 我已经告诉你时间复杂度了, 关于复杂度与流程图, 你分析一下程序,
一年多之前 回复
qq_22584569
qq_22584569 回复lbcab: 这是算法的完整版。流程图大神能搞出来嘛?时间复杂度怎么算?谢大神![图片说明](http://img.ask.csdn.net/upload/201604/08/1460098922_254954.png)[图片说明](http://img.ask.csdn.net/upload/201604/08/1460098928_289632.png)[图片说明](http://img.ask.csdn.net/upload/201604/08/1460098935_220215.png)
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!