网易游戏2013年校园招聘笔试题) -- 动态规划

http://blog.csdn.net/jdplus/article/details/20203641

题目地址:http://ac.jobdu.com/problem.php?pid=1531

题目描述:

小虎是游戏中的一个国王,在他管理的国家中发行了很多不同面额的纸币,用这些纸币进行任意的组合可以在游戏中购买各种装备来提升自己。有一天,他突然很想知道这些纸币的组合不能表示的最小面额是多少,请聪明的你来帮助小虎来解决这个财政问题吧。

输入:

输入包含多个测试用例,每组测试用例的第一行输入一个整数N(N<=100)表示流通的纸币面额数量,第二行是N个纸币的具体表示面额,取值[1,100]。

输出:

对于每组测试用例,输出一个整数,表示已经发行的所有纸币都不能表示的最小面额(已经发行的每个纸币面额最多只能使用一次,但面值可能有重复)。

样例输入:

5
1 2 3 9 100
5
1 2 4 9 100
5
1 2 4 7 100

样例输出:

7
8
15

使用0-1背包来解:

[cpp] view plaincopy

 #include <stdio.h> 
 #include <stdlib.h> 
 #include <string.h> 
  
 int N;  
 int value[101];  
 int dp[10001];  
 int max;  
  
 int Compare(const void * p, const void * q){  
  return *(int *)p - *(int *)q;  
 }  
  
 int Max(int a, int b){  
  return (a > b) ? a : b;  
 }  
  
 int ZeroOnePack(){  
  int i, j;  
     memset(dp, 0, sizeof(dp));  
  for (i = 1; i <= N; ++i){  
  for (j = max; j >= value[i]; --j){  
             dp[j] = Max(dp[j], dp[j-value[i]] + value[i]);  
         }  
     }  
  for (i = 1; i <= max; ++i)  
  if (dp[i] != i)  
  return i;  
 }  
  
 int main(void){  
  int i;  
  
  while (scanf("%d", &N) != EOF){  
         max = 0;  
  for (i = 1; i <= N; ++i){  
             scanf("%d", &value[i]);  
             max += value[i];  
         }  
         qsort(value, N, sizeof(int), Compare);  
         printf("%d\n", ZeroOnePack());  
     }  
  
  return 0;  
 }  

第二种解法:

[cpp] view plaincopy

 //动态规划的思想, 对于从第1个到第i个数的和total, 
 //如果第i+1个数大于total+1则不会组成total+1.  
 #include <stdio.h> 
 #include <stdlib.h> 
  
 int Compare(const void * p, const void * q){  
  return *(int *)p - *(int *)q;  
 }  
  
 int main(void){  
  int N;  
  int value[100];  
  int i;  
  int ans;  
  
  while (scanf("%d", &N) != EOF){  
  for (i = 0; i < N; ++i){  
             scanf("%d", &value[i]);  
         }  
         qsort(value, N, sizeof(int), Compare);  
         ans = 0;  
  for (i = 0; i < N; ++i){  
  if (value[i] > ans + 1){  
  break;  
             }  
  else 
                 ans += value[i];  
         }  
         printf("%d\n", ans + 1);  
     }  
  
  return 0;  
 }  

九度OJ上相似的题目:两船载物问题CODE代码片

V字仇杀队CODE代码片

参考资料:背包问题九讲

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一名叫大蕉的程序员

简约的JAVA版本MapReduce和日常No.25

昨天做了一个小调查,说看看想看些啥。大概的分布是这样的,一个1代表一个投票。看来还是2、3比较多。 11111 希望看到"算法"回复1。 111...

1975
来自专栏进击的程序猿

The Clean Architecture in PHP 读书笔记(二)

设计模式是对软件中通用问题的总结,有了设计模式,方便我们进行交流,譬如一说MVC,我们就知道是怎么回事了,不然我们必须巴拉巴拉一大堆话去描述,不易于传播、交流,...

834
来自专栏深度学习自然语言处理

【收藏】这些Python代码技巧,你肯定还不知道

人们还经常把 Python 笑称为「可执行伪码(executable pseudocode)」。但是,当你可以编写这样的代码时,很难去反驳这种言论:

853
来自专栏小樱的经验随笔

Vijos P1448 校门外的树【多解,线段树,树状数组,括号序列法+暴力优化】

校门外的树 描述 校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段...

5067
来自专栏腾讯IVWEB团队的专栏

响应式编程中 Stream 对象的实现原理

这篇文章介绍一种编程泛型,叫做响应式编程。将响应式称作“编程泛型”可能有些夸大其作用范畴,不过通过引入响应式确实会改变我们对特定问题的思考方法,就像刚接触red...

5580
来自专栏后端技术探索

php进阶

基本数据类型和数组都为真复制,即为真副本,当属性为对象时,为假复制,改变副本仍会影响原对象.解决方案:

1631
来自专栏Jimoer

Java设计模式学习记录-桥接模式

这次介绍结构型设计模式中的第二种模式,桥接模式。 使用桥接模式的目的就是为了解耦,松散的耦合更利于扩展,但是会增加相应的代码量和设计难度。

762
来自专栏WindCoder

异步JavaScript:从回调地狱到异步和等待

这是一个典型的异步编程挑战,您如何选择处理异步调用,在很大程度上,会导致或破坏您的应用程序,并且可能是您的整个启动。

6891
来自专栏十月梦想

node通过路由获取不同用户信息

具体功能:使用不同url判断是老师或者学生,老师的工号4-6位,学生学号8-10位,否则提示学号不正确,

834
来自专栏机器之心

Julia 1.0 正式发布,这是新出炉的一份简单中文教程

文章地址:https://zhuanlan.zhihu.com/p/41802723

3232

扫码关注云+社区

领取腾讯云代金券