01背包问题动态规划法求解
一问题描述：
有N件商品，每种商品都有各自的重量和价值，有一个背包，总容量是V。现在从这N种商品中挑选若干件放入背包中，要求每种商品最多放入一次，要使放入背包中商品总价值最大且商品总重量不超过背包容量，如何选择商品？
二解题思路
考虑将第i件商品放入背包之间背包的状态，此时，背包里有i-1件商品，最大的价值是f[v]。那么背包的最大价值应该是max{f[v],f[v-w[i]+c[i]}。
v是此时背包的容量，v可变，从0到V。w[i]是第i件商品的重量，c[i]是第i件商品的价值。也就是说当要将第i件商品放入背包之间背包的最大价值取决于背包之前的状态和第i件商品本身。
三动态规划法求解
#include<iostream>
#include<vector>
#include<set>
#include<cstdlib>
using namespacestd;
class Commodity //商品类
{
private:
int sequence; //商品序号
int weight; //商品重量
int cost; //商品价值
public:
static const int N; //商品总数
Commodity(int s=0,int w=0,int c=0)
{
sequence=s;
weight=w;
cost=c;
}
Commodity(const Commodity& c)
{
sequence=c.sequence;
weight=c.weight;
cost=c.cost;
}
const Commodity& operator=(constCommodity& c)
{
sequence=c.sequence;
weight=c.weight;
cost=c.cost;
return *this;
}
inline int getSequence() const
{
return sequence;
}
inline int getWeight() const
{
return weight;
}
inline int getCost() const
{
return cost;
}
inline void setSequence(int s=0)
{
sequence=s;
}
inline void setWeight(int w=0)
{
weight=w;
}
inline void setCost(int c=0)
{
cost=c;
}
};
const intCommodity::N=6;
class Bag
{
private:
int Volume; //背包总容量
vector<Commodity>CommoditySet; //商品集合
typedef struct Tag //关键算法所涉及的结构体
{
int v; //v=Volume...0
int value; //value是与v对应的装入背包中商品最大价值,如v=10,value=8表示此时背包容量是10,装入其中商品最大价值是8
set<int>sequence; //当达到最大价值v时,装入背包的商品编号
};
vector<Tag>tag;
bool AddToBag(int v,int sequence) //判断编号为sequence的商品是否能够加入背包中
//v表示背包的容量v=Volume...
{
if(v>=CommoditySet[sequence].getWeight())return true;
else return false;
}
bool AlterBagValue(intv,vector<Tag>::reverse_iterator it,int sequence) //修改背包的最大价值,前提是AddToBag函数返回真
{
intreminder=v-CommoditySet[sequence].getWeight(); //没有放入第i件商品前背包的重量
if(it->value<tag[reminder].value+CommoditySet[sequence].getCost())//此时应该放入第i件商品到背包中
{
it->value=tag[reminder].value+CommoditySet[sequence].getCost();
return true; //背包被修改,函数返回true
}
else return false; //背包没有被修改,函数返回false
}
void AddCommodityToBag(intv,vector<Tag>::reverse_iterator it,int sequence) //向背包中增加商品
{
intreminder=v-CommoditySet[sequence].getWeight();
set<int>::iterator it1;
it->sequence.clear(); //很重要,必须把当前的商品编号清空
for(it1=tag[reminder].sequence.begin();it1!=tag[reminder].sequence.end();it1++)
{
it->sequence.insert(*it1);
}
it->sequence.insert(sequence);
}
void ShowCommodity(int sequence) //显示编号是sequence的商品信息
{
ints=CommoditySet[sequence].getSequence();
intw=CommoditySet[sequence].getWeight();
intc=CommoditySet[sequence].getCost();
cout<<"背包里商品信息: ";
cout<<"编号:"<<s<<" ";
cout<<"重量:"<<w<<" ";
cout<<"价值:"<<c<<endl;
}
public:
Bag(int V):Volume(V)
{
int i;
int w,c;
for(i=0;i<Commodity::N;i++)
{
cout<<"请输入第"<<i<<"件商品的重量:";
cin>>w;
if(!cin.good()) exit(1);
cout<<"请输入第"<<i<<"件商品的价值:";
cin>>c;
if(!cin.good()) exit(1);
Commodity commodity(i,w,c);
CommoditySet.push_back(commodity);
}
for(i=0;i<=Volume;i++)
{
Tag t;
t.v=i;
t.value=0;
t.sequence.clear();
tag.push_back(t);
}
}
void Solution() //用动态规划法解决背包问题
{
int i;
int v;
vector<Tag>::reverse_iteratorit; //反向迭代器
for(i=0;i<Commodity::N;i++)
{
for(v=Volume,it=tag.rbegin();AddToBag(v,i)&& it!=tag.rend();it++,v--)
{
//当背包确实被修改时,才应该增加商品
if(AlterBagValue(v,it,i)) AddCommodityToBag(v,it,i);
}
}
}
void showResult()
{
vector<Tag>::reverse_iteratorit;
set<int>::const_iterator it1;
int v,value;
for(it=tag.rbegin();it!=tag.rend();it++)
{
v=it->v;
value=it->value;
cout<<"当背包重量是"<<v<<"时背包里商品最大价值是"<<value<<endl;
for(it1=it->sequence.begin();it1!=it->sequence.end();it1++)
{
ShowCommodity(*it1);
}
}
}
};
void main()
{
Bag bag(40);
bag.Solution();
bag.showResult();
}
四测试
背包容量是40，选取数据测试
当背包容量是30
选取数据测试
标签：01,sequence,int,规划法,value,商品,背包,it1 From： https://blog.51cto.com/u_15899033/5903532