注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

HDU 2546 0-1背包问题  

2012-10-05 22:53:27|  分类: 动态规划 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=2546

背包问题是一个经典的动态规划模型。它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,故不少教材都把它作为动态规划部分的第一道例题。

01背包问题,可以这么理解。

题目

有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]}

这 个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题, 若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物 品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此 时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。


优化空间复杂度

以上方法的时间和空间复杂度均为O(VN),其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到O。

先 考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组 f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1] [v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。伪代码如下:

for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}
,因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。

事实上,使用一维数组解01背包的程序在后面会被多次用到,所以这里抽象出一个处理一件01背包中的物品过程,以后的代码中直接调用不加说明。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int i, j;
int m, n, max, v, maxz;
int w[1001], p[1001];
while(1)
{
memset(p, 0, sizeof(p));
scanf("%d", &n);
if(n == 0)
break;
maxz = 0;
for(i = 0; i < n; i++)
{
scanf("%d", &w[i]);
if(w[i] > w[maxz])
maxz = i;
}
scanf("%d", &m);
if(m < 5)
{
printf("%d\n",m);
continue;
}
v = m - 5;
for(i = 0; i < n; i++)
{
if(i != maxz)
for(j = v; j >= w[i]; j--)
{
if(p[j - w[i]] + w[i] > p[j] )
p[j] = p[j - w[i]] + w[i];
}
}
printf("%d\n",m - p[v] - w[maxz]);
}
return 0;
}



  评论这张
 
阅读(495)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018