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

bear_fish

发布于 2018-09-18 11:21:07

3780

发布于 2018-09-18 11:21:07

文章被收录于专栏：用户2442861的专栏用户2442861的专栏

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 plain copy

 #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 plain copy

 //动态规划的思想, 对于从第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代码片

参考资料：背包问题九讲

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2014年12月18日，如有侵权请联系 cloudcommunity@tencent.com 删除

其他