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

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

01背包的初值  

2011-09-23 20:53:11|  分类: ACM_动态规划 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
以一道题为例吧,因为这道题用到了01背包,但是初值搞的不好,弄了很长时间

最小邮票数

题目描述

    有若干张邮票,要求从中选取最少的邮票张数凑成一个给定的总值。
    如,有1分,3分,3分,3分,4分五张邮票,要求凑成10分,则使用3张邮票:3分、3分、4分即可。

输入

    首先是要求凑成的邮票总值M,M<100。然后是一个数N,N〈20,表示有N张邮票。接下来是N个正整数,分别表示这N张邮票的面值,且以升序排列。

输出

    能够凑成总值M的最少邮票张数。若无解,输出0。

样例输入

10 5 1 3 3 3 4

样例输出

3

是个很水的01背包,要求恰好装满背包,
背包九讲中有讲到过
要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果是未经常数优化过的背包,则初值的时候需要除了f[0][0] = 0外,其他都为最大,

经过常数优化的代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m;
int f[1000];
int c[100];

void init()
{
        scanf("%d",&n);
        int i;
        for(i = 1;i <= n;i ++)
        {
                scanf("%d",&c[i]);
        }
}

int min(int x,int y)
{
        return x < y ? x : y;
}

void work()
{
        memset(f,0x3f,sizeof(f));
        int i,j;
        f[0] = 0;//只有f[0] = 0
        for(i = 1;i <= n;i ++)
        {
                for(j  = m;j >= c[i];j --)
                {
                        f[j] = min(f[j],f[j-c[i]]+1);
                }
        }
        if(f[m] != 1061109567)
        printf("%d\n",f[m]);
        else
        printf("0\n");
}


int main()
{
        while(scanf("%d",&m) != EOF)
        {
                init();
                work();
        }
        return 0;
}

未经过常数优化的代码
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int m,n;
int dp[1000][1000];
int c[100];

void init()
{
        scanf("%d",&n);
        int i;
        for(i = 1;i <= n;i ++)
        {
                scanf("%d",&c[i]);
        }
}

int min(int x,int y)
{
        return x < y ? x : y;
}

void work()
{
        int i;
        int j;
        memset(dp,0x3f,sizeof(dp));
        dp[0][0] = 0;//只有dp[0][0]为0!

        for(i = 1;i <= n;i ++)
        {

                for(j = 0;j <= m;j ++)
                {
                        dp[i][j] = dp[i-1][j]; //注意要是用二维的化,这里需要把前一次的状态保留下来!!!在这里WA了好几次
                        if( j >= c[i])
                        dp[i][j] = min(dp[i][j],dp[i-1][j-c[i]] + 1 );
                }
        }

        for(i = 1;i <= n;i ++)
        {
                for(j = 1;j <= m;j ++)
                {
                        printf("%d ",dp[i][j]);
                }
                printf("\n");
        }


}


int main()
{
        while(scanf("%d",&m) != EOF)
        {
                init();
                work();
        }

        return 0;
}
*/


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

历史上的今天

评论

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

页脚

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