POJ 1252 Euro Efficiency

POJ 1252 Euro Efficiency

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

背包 要么 BFS

意大利是说给你几个基本的货币,组成 1~100 所有货币,使用基本上的货币量以最小的。

出口 用法概率。和最大使用量。

能够BFS 有可能 。

只是记得数组开大点。 可能会出现 100 = 99+99 -98 的情况。

背包是先做一个全然背包,求得最少可能由多少相加。

然后做一个 01背包,看是否能被 减。

背包:

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int dp[10002];

int value[7];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int m=10001;
        for(int i=0; i<6; i++)
            scanf("%d",&value[i]);
        for(int i=1; i<m; i++)
            dp[i]=10001;
        dp[0]=0;
        for(int i=0; i<6; i++)
        {
            for(int j=value[i]; j+value[i]<m; j++)
            {
                dp[j]=min(dp[j-value[i]]+1,dp[j]);
//                printf("%d :%d==\n",j,dp[j]);
            }

        }

        for(int i=0; i<6; i++)
        {
            for(int j=m-value[i]; j>0; j--)
            {
                dp[j]=min(dp[j+value[i]]+1,dp[j]);
//                printf("%d :%d==\n",j,dp[j]);
            }

        }

        double ans=0;
        int maxn=0;
        for(int i=1; i<=100; i++)
        {
//            printf("%d : %d\n",i,dp[i]);
            ans+=dp[i];
            maxn=max(maxn,dp[i]);
        }
        printf("%.2f %d\n",ans/100.0,maxn);
    }
}

BFS:

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
struct lx
{
    int ans,lv;
};
int ans[2051];
int value[7];
void bfs()
{
    queue<lx>q;
    bool vis[2051];
    memset(vis,0,sizeof(vis));
    lx now,tmp;
    tmp.ans=0,tmp.lv=0;
    q.push(tmp);
    vis[0]=1;
    while(!q.empty())
    {
        tmp=q.front();q.pop();
        ans[tmp.ans]=tmp.lv;
        for(int i=0;i<6;i++)
        {
            int num1=tmp.ans+value[i];
            int num2=tmp.ans-value[i];
            now.lv=tmp.lv+1;
            if(!vis[num1]&&num1>0&&num1<2000)
            {
                vis[num1]=1;
                now.ans=num1;
                q.push(now);
            }
            if(!vis[num2]&&num2>0&&num2<2000)
            {
                vis[num2]=1;
                now.ans=num2;
                q.push(now);
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0; i<6; i++)
            scanf("%d",&value[i]);

        bfs();
        double an=0;
        int maxn=0;
        for(int i=1;i<=100;i++)
        {
            an+=ans[i];
            maxn=max(maxn,ans[i]);
//            printf("%d : %d\n",i,ans[i]);
        }
        printf("%.2f %d\n",an/100,maxn);
    }
}

版权声明:本文博客原创文章。博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117264.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux hook技术[通俗易懂]

    linux hook技术[通俗易懂]Hook中文翻译为钩子,可以用来截获调用函数,并改变函数的行为。Windows和Linux都提供了相应的实现机制。这篇文章是针对Linux平台的。也是在学习协程库libco过程中接触到的。正文:如果你是一个开发者,并期望去改变一个库函数的行为,那么这篇文章将带你入门——只是用库函数做实验。所有的代码是用C写的,在Linux上面使用GCC编译测试。根据维基百科,“在计算机…

  • 将链接地址转换为二维码并且复制文字_二维码怎么转换成链接

    将链接地址转换为二维码并且复制文字_二维码怎么转换成链接前言:我的需求是讲链接地址转换成二维码,供用户去使用并展示H5端,这里会说到一些小细节,先上代码吧~1.html结构2.生成二维码3.复制二维码要注意的一点是:首先二维码的密度是根据参数的多少来显示的,参数如果特别多,就会导致二维码密度太密,用户拿手机是扫不出来的.解决方案:1.要后端或者自己写一个接口专门放这些地址,可以理解成压缩.然后拿到压缩的东西再去转码.2.把在另外一端能获取到的参数,通过方式获取到,在转码的时候尽量减少参数的携带,带上必要..

  • Android布局优化之ViewStub、include、merge使用与源码分析

    Android布局优化之ViewStub、include、merge使用与源码分析在开发中UI布局是我们都会遇到的问题,随着UI越来越多,布局的重复性、复杂度也会随之增长。首先用得最多的应该是include,按照官方的意思,include就是为了解决重复定义相同布局的

  • 常见排序算法的稳定性「建议收藏」

    快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。其次,说一下稳定性的好处。排序

  • Oracle基础 各种语句的定义格式

    Oracle内建数据类型一、 字符数据1、 char(size)2、 varchar2(size) 最常用,最大长度4000字节3、 nvhar(size)、nvarchar(size)4、 varc

    2021年12月20日
  • fstream 获取文件大小_c++获取文件大小

    fstream 获取文件大小_c++获取文件大小fstream获得文件大小

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号