背包问题(01,完全,多重,未测试)
#define MAXN 120005 //maxcash
#define MAX 11
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n[MAX],c[MAX];//n[i]物品i的数量,c[i]费用,w[i]价值
int f[MAXN];//MAXN为最大容量 ,存储状态值
int V,N;//V最大容量,N物品个数
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*01背包物品 */
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void ZeroOnePack(int cost,int weight)
{
//一件01背包物品
// 费用cost, 价值weight,01背包
for(int v=V;v>=cost;--v)
f[v]=max(f[v],f[v-cost]+weight);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void ZeroOnePackMain()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*N件物品 容量为V的背包,第i件物品费用c[i],价值w[i],求转入背包可以获取的最大价值
原方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
简化方程:f[v]=max{f[v],f[v-cost]+weight};
*/
for(int i=0;i<N;i++)
ZeroOnePack(cost[i],weight[i]);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*一件完全背包*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void CompletePack(int cost,int weight)
{
//一件物品完全背包
//N 种物品 容量 V,c[i],w[i], 每一种无限,求最大价值
// 费用cost, 价值weight,完全背包
//对多种物品的问题,可以添加的优化:a.去掉大于V的物品;b.c[i]<=c[j] and w[i]>=w[j]去掉物品j
for(int v=cost;v<=V;++v)
f[v]=max(f[v],f[v-cost]+weight);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*一件多重背包*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MultiplePack(int cost,int weight,int amount)
{
//多重背包
//1种物品 费用cost, 价值weight,个数amount
//二进制优化log(amount)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(c*amount>=V)
{
CompletePack(cost,weight);
return;
}
int k=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(k<amount)
{
ZeroOnePack(k*cost);
amount-=k;
k*=2;
}
ZeroOnePack(amount*cost);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2009-03-18 23:35
爬 阅读(1839)
评论(2) 编辑 收藏 引用 所属分类:
Dynamic programming