背包問題（01，完全，多重，未測試）
#define MAXN 120005 //maxcash
#define MAX 11
int n[MAX],c[MAX];//n[i]物品i的數(shù)量，c[i]費(fèi)用，w[i]價值
int f[MAXN];//MAXN為最大容量 ，存儲狀態(tài)值
int V,N;//V最大容量，N物品個數(shù)
/**//*01背包物品 */
void ZeroOnePack(int cost,int weight)
{
//一件01背包物品
// 費(fèi)用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件物品費(fèi)用c[i]，價值w[i],求轉(zhuǎn)入背包可以獲取的最大價值
原方程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], 每一種無限,求最大價值
// 費(fèi)用cost， 價值weight，完全背包
//對多種物品的問題，可以添加的優(yōu)化：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種物品 費(fèi)用cost， 價值weight，個數(shù)amount
//二進(jìn)制優(yōu)化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
爬 閱讀(1872)
評論(2) 編輯 收藏 引用 所屬分類:
Dynamic programming