NC211229. E、爱玩游戏的Tom
描述
Tom很喜欢玩游戏，他在电脑上下了《GTA5》和《微软飞行模拟》，对于后者他还丧心病狂的下载了所有地图包，导致他可用空间只有mGM，但他还有几个学校要求安装的软件没有下载，他不能全部放下去，因此只能选择性的安装一部分。现在，我们知道每个学习软件的大小以及该学习软件的重要程度，现在Tom找到你，应该安装哪一些软件，使得这些软件的重要程度之和最大。对于输入第一行有n（0 < n < 100）和m(0 < m < 10000)两个整数组成，n代表接下来的输入行数，m代表可用空间还剩mGB。接下来的n行，每行两个整数，前一个整数为每个学习软件的大小（GB），后一个整数代表重要程度。对于输出，只有一行，即为最大重要程度之和。
输入描述
第一行输入n和m，n代表接下来的行数，m代表可用空间剩余内存，整数之间空格隔开接下来的n行，由两个整数组成，前一个为每个软件大小，后一个整数代表重要程度，整数之间空格隔开
输出描述
输出只有一行且只有一个整数，即为最大重要程度之和
示例1
输入:
3 23 15 9 20 5 7 7
输出:
16
说明:
1、输入：
第一行3表示接下来有3行，23表示还剩23GB
第一行后的三行前一个整数表示学习软件大小（GB），后一个整数表示重要程度
2、输出：
16，表示最大重要程度之和，安装的软件为15GB的和7GB的
C++ 解法, 执行用时: 3ms, 内存消耗: 400K, 提交时间: 2021-08-04 23:42:49
#include<bits/stdc++.h>
using namespace std;
long long dp[10010],n,m,w,v,i,j;
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++){ cin>>v>>w;for(j=m;j>=v;j--)dp[j]=max(dp[j],dp[j-v]+w);}cout<<dp[m];
}
Python3(3.9) 解法, 执行用时: 153ms, 内存消耗: 3772K, 提交时间: 2020-10-27 15:25:40
I=lambda:map(int,input().split())
n,space=I()
f=[0]*(space+1)
for _ in range(n):
size,value=I()
for i in range(space,size-1,-1):
f[i]=max(f[i],f[i-size]+value)
print(f[space])