大一下c语言期末考试编程题（初级编程小学生竞赛真题）

时间限制: 1 Sec 内存限制: 128 MB

题目描述

托塔李天王的三太子那吒，本领高强，他要赶在奥林匹克运动会之际，开一个头脑奥林匹克比赛，获胜者的奖品就是经过提练后的“氦-3”晶结体；该物质在月球上大量存在，是一种无色、无味的氦气同位素，它在核聚变研究中有重要作用。氦-3还是一种绝对清洁的能源，因为它本身不带放射性，因此不会产生任何放射性废料。可是如何从月球上将该晶体运回地球呢？那吒说：用我的肚兜吧！当然他的肚兜易受太阳风等因素的影响，载重量不能超过K(1≤n≤100000)，超过这个值，肚兜就不会飞了；这个K值那吒会告诉你的，同时还会告诉你每一个晶体的重量。 你的任务是使这个肚兜一次能运回更多的晶体。

输入

有两行： 第一行有两个正整数n(1≤n≤100。)和k，用一个空格隔开。表示有n个晶体，肚兜最大载重量为k。 第二行有n个不超过10000的正整数，分别表示n个晶体的重量，数与数之间用一个空格隔开。

输出

只有一行，该行只有一个正整数，表示那吒的肚兜一次能运回的晶体重量的最大值。

样例输入 Copy

5 15 2 4 4 8 10

样例输出 Copy

14

V

V

V

V

V

V

V

V

V

解答：

#include<bits/stdc .h> using namespace std; int dp[1000001]; int main() { int t,n,c,i; scanf("%d%d",&n,&t); while(n--) { scanf("%d", &c); for (i=t;i>=c;--i) // 填满型背包 { dp[i]=max(dp[i],c dp[i-c]); } } printf("%d",dp[t]); return 0; }