题目描述

AC鸭从山洞中带回了一大堆金币，成为了鸭国首富。

AC鸭的钱实在太多了，于是它背着特制的背包前往超市采购。

超市中共有 n 个物品，每个物品都有一个花费ci ​和价值 wi ​（由于这家超市专为富豪服务，所以东西很贵，ci ​可能会很大）。

AC鸭的背包是高科技定制版（花费 99999999 99999999 元），可以装下任意 m 件物品。AC鸭想知道，它在花费不超过 C 的情况下，最多能购买多少价值的商品。

输入

第一行给出三个整数 n , m , C n,m,C，表示商品个数，背包容量和花费限制。 接下来 n n 行，每行给出一个商品的信息，包括花费ci ​ 和价值 wi ​ .

输出

输出仅一个整数，表示购买商品的最大价值和。

样例 输入数据 1 5 3 1000
234 5
429 6
195 4
735 10
519 7

输出数据 1

16

我的程序

#include<iostream>
using namespace std;
long long n,m,C,v[100010],w[100010],f[10010][10010];
int main(){
	cin>>n>>m>>C;
	for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=C;j++){
			f[i][j]=f[i-1][j];
			f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
		}
	cout<<f[n][m]<<endl;
	return 0;
}