MyException - 我的异常网
当前位置:我的异常网» 综合 » hdu 2844(双肩包)

hdu 2844(双肩包)

www.MyException.Cn  网友分享于:2013-10-17  浏览:2次
hdu 2844(背包)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[100010],w[110],c[110];
int main()
{
    int n,m,i,j,k,cnt;
    while( scanf("%d%d",&n,&m),n+m )
    {
        cnt=0;
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++) scanf("%d",&w[i]);
        for(i=1;i<=n;i++) scanf("%d",&c[i]);
        for(i=1;i<=n;i++)
        {
            if( c[i]*w[i] > m )  // 完全背包
            {
                for( j=w[i];j<=m;j++ )
                    dp[j]= max( dp[j],dp[j-w[i]]+w[i] );
            }
            else //多重背包 转化为 01背包 ,把物品的个数 c[i] 拆分为2^0,2^1,……,2^k,c[i]-2^k+1; 1至c[i]中的数肯定能够分解为前面的数的和。就是十进制转二进制
            {
                k=1;               
                int num=c[i];
                while( k < num )
                {
                    for( j=m; j>=k*w[i] ; j--)
                        dp[j]=max( dp[j],dp[j-k*w[i]]+k*w[i]);  //拆分是对c[i]来说的,具体操作时其实是把2^k个物品组合为一个物品来操作
                    num-=k;
                    k<<=1;
                }
                for( j=m;j>=num*w[i];j--)
                    dp[j]=max( dp[j],dp[j-num*w[i]]+num*w[i] );
            }
        }
        for(i=1;i<=m;i++) if( dp[i]==i ) cnt++;
        printf("%d\n",cnt);
    }
    return 0;
}


文章评论

做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员都该阅读的书
程序员都该阅读的书
Java程序员必看电影
Java程序员必看电影
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
我是如何打败拖延症的
我是如何打败拖延症的
代码女神横空出世
代码女神横空出世
漫画:程序员的工作
漫画:程序员的工作
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
10个调试和排错的小建议
10个调试和排错的小建议
中美印日四国程序员比较
中美印日四国程序员比较
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
一个程序员的时间管理
一个程序员的时间管理
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员应该关注的一些事儿
程序员应该关注的一些事儿
鲜为人知的编程真相
鲜为人知的编程真相
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
每天工作4小时的程序员
每天工作4小时的程序员
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
编程语言是女人
编程语言是女人
程序员必看的十大电影
程序员必看的十大电影
为什么程序员都是夜猫子
为什么程序员都是夜猫子
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
我的丈夫是个程序员
我的丈夫是个程序员
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
 程序员的样子
程序员的样子
旅行,写作,编程
旅行,写作,编程
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有