[NOIP2006]开心的金明

输入第1行，为两个正整数，用一个空格隔开：N m（其中N表示总钱数，m为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格，p表示该物品的重要度）

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 464K, 提交时间: 2020-07-02 17:15:49

#include<bits/stdc++.h>
using namespace std;
int dp1[30005],v,p,N,m;
int main(){
	cin>>N>>m;
	for(int i=1;i<=m;i++){
		cin>>v>>p;
		for(int j=N;j>=v;j--)
			dp1[j]=max(dp1[j],dp1[j-v]+v*p);
			
	}
	cout<<dp1[N];
}

Pascal(fpc 3.0.2) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2018-09-07 20:50:22

var n,m,i,j,x,y:longint;
f:array[0..30000]of longint;
begin
readln(m,n);
for i:=1 to n do
begin
readln(x,y);
for j:=m downto x do
  if f[j-x]+x*y>=f[j] then f[j]:=f[j-x]+x*y;
end;
writeln(f[m]);
end.

Python3 解法, 执行用时: 379ms, 内存消耗: 5876K, 提交时间: 2023-05-25 21:22:21

n, m = map(int, input().split())
dp = [0]*(n+1)
for _ in range(m):
    v, p = map(int, input().split())
    for i in range(n, v-1, -1):
        dp[i] = max(dp[i], dp[i-v] + v*p)
        
print(dp[n])

详情