MLE力

题目：有 n 件货物，它们的重量分别为 W 1 ​ ,W 2 ​ ,...,W n ​ ，价值分别为 P 1 ​ ,P 2 ​ ,...,P n ​

有一辆载重为 V 的货车，司机想从这 n 件货物中选取若干件，使得货车 满载（即所载货物重量之和恰好为 V ）而归。求：车上货物的总价值最大为多少？

范围：1≤V≤100000 ，1≤n≤100，1≤W≤10000 ，1≤P≤1000

#include<bits/stdc++.h>
using namespace std;
int v,n,s[101],w[101],f[101][100001];
int main(){
	scanf("%d%d",&v,&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&s[i]);
	for(int i=0;i<=n;i++)
		for(int j=1;j<=v;j++) f[i][j]=-1;
    f[1][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=v;j++)
			if(j>=w[i]){
				if(f[i-1][j-w[i]]==-1) f[i][j]=f[i-1][j];
				else f[i][j]=max(f[i-1][j-w[i]]+s[i],f[i-1][j]);
			}	
			else f[i][j]=f[i-1][j];
	}
	if(f[n][v]==-1) printf("0");
	else printf("%d",f[n][v]);
	return 0;
}