POJ 1276 Cash Machine 解答-阿里云开发者社区

开发者社区> fjie> 正文

POJ 1276 Cash Machine 解答

简介: 题目详见: http://poj.org/problem?id=1276 这道题与POJ 1014同属一类题, 区别在于POJ 1014的解是求恰好等于容量的情况, 而这道题较为常规, 同时这道题的数据较大, 套用我在博客http://blog.
+关注继续查看

题目详见: http://poj.org/problem?id=1276

这道题与POJ 1014同属一类题, 区别在于POJ 1014的解是求恰好等于容量的情况, 而这道题较为常规, 同时这道题的数据较大, 套用我在博客http://blog.csdn.net/hfut_jf/article/details/18190521里写的程序会出现Time Limit Exceeded错误, 必须加以优化, 先贴出原先的程序, 在与最后AC的代码比较, 主要看代码如何改进:

改进前代码(会出现Time Limit Exceeded错误):

#include <iostream>
using namespace std;
const int n=1001;
int main(int argc, char * argv[])
{
    int cash=0, N=0;
	int num[n]; // 每种面值钞票张数
	int d[n]; // 每种钞票对应面值
	int v[100001]; // 背包容量 
	int w[100]; // 压缩用数组

    memset(num, 0, sizeof(num));
    memset(d, 0, sizeof(d));
    while(true){
        // 初始化
        memset(v, 0, sizeof(v));
        
        cin>>cash>>N;
        for(int i=0;i<N;++i){
			cin>>num[i]>>d[i];
		}
		int k=0; // 记录压缩后替代物品数 
		// 二进制压缩
		for(int i=0;i<N;++i){
            int t=1;
            while(num[i]>0){
                if(num[i]>t){
                    num[i]-=t;
                    w[k++]=t*d[i];
                    t*=2;
                }else{
                    w[k++]=num[i]*d[i];
                    num[i]=0;      
                }        
            }
        }
        
        // 执行动态规划算法
        for(int i=0;i<k;++i){
            for(int j=cash;j>=w[i];--j){  
                if(v[j]<v[j-w[i]]+w[i])
                    v[j]=v[j-w[i]]+w[i];
            }
        }
        cout<<v[cash]<<endl; 
    }
    return 0;   
}
改进后代码(已AC):

#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
    int cash=0, N=0;
	int num[1001];
	int d[1001];
	int v[100001];
    while(cin>>cash>>N){
        memset(v, 0, sizeof(v)); 
        for(int i=0;i<N;++i){
			cin>>num[i]>>d[i];
		    int w=0,t=1;
            while(num[i]>0){
                if(num[i]>t){
                    num[i]-=t;
                    w=t*d[i];
                    t*=2;
                }else{
                    w=num[i]*d[i];
                    num[i]=0;      
                }
                for(int j=cash;j>=w;--j){  
                    if(v[j]<v[j-w]+w)
                        v[j]=v[j-w]+w;
                }        
            } 
        }
        cout<<v[cash]<<endl; 
    }
    return 0;   
}
主要改进:

在一种币值钞票输入后即进行二进制压缩和动态规划计算, 减少了循环次数及所需存储空间.

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
HSF/Dubbo序列化时的LocalDateTime, Instant的性能问题
### 来源 在对Dubbo新版本做性能压测时,无意中发现对用例中某个TO(Transfer Object)类的一属性字段稍作修改,由Date变成LocalDateTime,结果是吞吐量由近5w变成了2w,RT由9ms升指90ms。
2331 0
计算机图形学遇上深度学习
今日,TensorFlow 宣布推出 TensorFlow Graphics,该工具结合计算机图形系统和计算机视觉系统,可利用大量无标注数据,解决复杂 3D 视觉任务的数据标注难题,助力自监督训练。
2286 0
独家揭秘:阿里小程序的一云多端!看这篇就够了!
阿里巴巴小程序一云多端的整体战略,以及阿里小程序后续为开发者提供的云服务(云应用、云开发等)、开发者工具链(IDE、插件、SDK等)、跨端框架能力说明。同时结合繁星计划后续提供给开发者的扶持和ISV的权益体系做一个整体的介绍。
27362 0
CDN的HTTPS配置及故障排除
相较于HTTP协议来说,HTTPS协议在网络链路中传输更具有安全可靠性,因为它通过SSL证书在链路中间对我们七层的网络包做了加密,进而防止了一些恶意的内容劫持。针对于这种场景,阿里云CDN也提供了相关的功能,可以支持客户端到CDN L1节点的HTTPS的协议。
1574 0
GDB 调试 Mysql 实战(一)源码编译安装
下载源码 git clone https://github.com/mysql/mysql-server.git cd mysql-server git checkout 5.7 编译安装 安装依赖 yum install -y cmake make gcc gcc-c++ ncurses-dev...
979 0
PostgreSQL 锁
锁的类型 /* NoLock is not a lock mode, but a flag value meaning "don't get a lock" */ #define NoLock 0 #define AccessS...
1140 0
+关注
fjie
计算机学生,研究方向为数据挖掘与机器学习,现阶段主要兴趣为深度学习方法在图/网络等非常规(non Euclidean domain)数据中的应用。Github pages: flycser.github.io,Email: hfut_jf@aliyun.com
68
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载