syhd142  
日历
<2014年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
0/1背包问题的最简单特殊情况,重量和价值相等。要求输出放入了哪些物品,顺序和输入的时候相同,这样从DP的时候从后面往前面递推就好了。
背包问题可以只用一个一维数组表示,这样节省空间。
#include <stdio.h>
#include 
<string.h>

#define W 10005

int c[W], l[25];
bool p[25][W];

int main()
{
    
int w, n;
    
while(~scanf("%d"&w))
    {
        scanf(
"%d"&n);
        
for(int i = 1; i <= n; i++)
            scanf(
"%d"&l[i]);
        
        memset(c, 
0sizeof(c));
        memset(p, 
0sizeof(p));
        
        
for(int i = n; i; i--)
        
for(int j = w; j >= l[i]; j--)
        {
            
if(c[j] < c[j - l[i]] + l[i])
            {
                c[j] 
= c[j - l[i]] + l[i];
                p[i][j] 
= 1;
            }
        }
        
for(int i = 1, j = w; i <= n; i++)
            
if(p[i][j])
            {
                printf(
"%d ", l[i]);
                j 
-= l[i];
            }
        printf(
"sum:%d\n", c[w]);
    }
    
return 0;
}
posted on 2010-06-30 10:59 Fucker 阅读(1138) 评论(7)  编辑 收藏 引用 所属分类: ACM/ICPCDP
评论:
  • # re: UVA 624 CD   Posted @ 2010-10-27 18:41
    为什么从后面往前就好了?  回复  更多评论   

  • # re: UVA 624 CD   Posted @ 2010-10-27 18:42
    请加我QQ吧 406500921  回复  更多评论   

  • # re: UVA 624 CD  Fucker Posted @ 2010-10-27 23:03
    @想
    看看背包9讲,里面说的很详细。
    因为是0/1背包,所以从后往前推。
    如果是完全背包就从前往后推。  回复  更多评论   

  • # re: UVA 624 CD  alien Posted @ 2011-03-31 13:57
    最后一组数据好像通不过。
    45 8 4 10 44 43 12 9 8 2
    这组我用你的程序计算出来的是43 2 sum:45.
    应该是4 10 12 9 8 2 sum:45
    为什么可以这样记录路径?  回复  更多评论   

  • # re: UVA 624 CD  Fucker Posted @ 2011-03-31 14:32
    @alien
    额,有点遥远了,都忘记了。  回复  更多评论   

  • # re: UVA 624 CD  kokosy Posted @ 2012-09-19 20:24
    @alien
    输出任意一条路径就行  回复  更多评论   

  • # re: UVA 624 CD  网友 Posted @ 2014-04-27 11:50
    为什么枚举顺序要和打印顺序相反呢?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © Fucker Powered by: 博客园 模板提供:沪江博客