背包问题（01，完全，多重，未测试）
#define MAXN 120005 //maxcash
#define MAX 11
int n[MAX],c[MAX];//n[i]物品i的数量，c[i]费用，w[i]价值
int f[MAXN];//MAXN为最大容量 ，存储状态值
int V,N;//V最大容量，N物品个数
/**//*01背包物品 */
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;
}
void ZeroOnePackMain(){
/**//*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;
}
/**//*一件完全背包*/
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;
}
/**//*一件多重背包*/
void MultiplePack(int cost,int weight,int amount){
//多重背包
//1种物品 费用cost， 价值weight，个数amount
//二进制优化log(amount)
if(c*amount>=V){
CompletePack(cost,weight);
return;
}
int k=1;
while(k<amount){
ZeroOnePack(k*cost);
amount-=k;
k*=2;
}
ZeroOnePack(amount*cost);
return;
}
posted on 2009-03-18 23:35
爬 阅读(1843)
评论(2) 编辑 收藏 引用 所属分类:
Dynamic programming