首页 > 代码库 > 【HDOJ】2546 饭卡
【HDOJ】2546 饭卡
01背包,需要先对数据升序排序。这样保证优先购买最贵的东西,才满足背包条件。
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 5 #define MAXNUM 1005 6 7 int prices[MAXNUM]; 8 int dp[MAXNUM]; 9 10 int mymax(int a, int b) { 11 return a>b ? a:b; 12 } 13 14 int comp(const void *a, const void *b) { 15 return *(int *)b - *(int *)a; 16 } 17 18 int main() { 19 int n, m; 20 int i, j, tmp; 21 22 while (scanf("%d", &n)!=EOF && n) { 23 for (i=1; i<=n; ++i) { 24 scanf("%d", &prices[i]); 25 } 26 27 scanf("%d", &m); 28 29 if (m < 5) { 30 printf("%d\n", m); 31 continue; 32 } 33 34 qsort(prices+1, n, sizeof(int), comp); 35 memset(dp, 0, sizeof(dp)); 36 37 for (i=1; i<=n; ++i) { 38 for (j=m; j>=5; --j) { 39 tmp = j - prices[i]; 40 if (tmp >= 5) { 41 dp[j] = mymax(dp[tmp]+prices[i], dp[j]); 42 } else { 43 dp[j] = mymax(prices[i], dp[j]); 44 } 45 } 46 } 47 48 printf("%d\n", m-dp[m]); 49 } 50 51 return 0; 52 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。