DP实例之01背包问题C语言实现
####问题描述：
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
用二维数组记录每个子问题的值，避免重复计算，行从0到N，列从0到V。f[][0]=0,f[0][]=0;
很容易算出01背包的时间和空间复杂度，O(V*N)。
C语言代码实现如下：
int Bag()
{
int i,j;
int num=4; //有4个物品
int vol=10; //背包容量为10
int w[5]={0,3,1,4,3}; //此处需要多添加一个首元素元素0，因为下面的循环从1开始，若不添加0，则i-1会出现数组越界
int v[5]={0,1,3,4,2};//此处需要多添加一个首元素元素0，因为下面的循环从1开始，若不添加0，则i-1会出现数组越界
int f[5][11]={0}; //用来保存结果 ，以上几个数组长度都比num，vol多一个
for(i=1;i<=num;i++) //状态方程
{
for(j=1;j<=vol;j++)
{
if (w[j]>j) //如果第i个物品放不进背包
f[i][j]=f[i-1][j];
else if(f[i-1][j]>(f[i-1][j-w[i]]+v[i])) //状态方程 取<span style="font-size: 14px;">max{f[i-1][v],f[i-1][v-c[i]]+w[i]}</span>
f[i][j]=f[i-1][j];
else
f[i][j]=f[i-1][j-w[i]]+v[i];
}
}
return f[4][10];
}
blog comments powered by Disqus
发布日期
2012-11-02