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

Question

#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;

}

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

Answer 1

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

关于经典的背包问题, 有一个转移方程: 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.
应该够详细了.....