acwing.【完全背包问题】(dp)

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
#include<stdio.h>

using namespace std;
int vi[1010],wi[1010];
long long dp[1010][1010];
long long dfs(int i,int j){
	long long res=0;
	if(dp[i][j]!=0){
		return dp[i][j];
	}
	if(i==0){
		res=0;
	}
	else if(j<wi[i]){
		res=dfs(i-1,j);
	}
	else{
		for(int n=0;n*wi[i]<=j;n++){
			res=max(res,dfs(i-1,j-wi[i]*n)+vi[i]*n);
		}
	}
	dp[i][j]=res;
	return res;
}
int main(){
	int N,V;
	cin>>N>>V;
	for(int i=1;i<=N;i++){
		int v,w;
		cin>>v>>w;
		vi[i]=w;
		wi[i]=v;
	}
	cout<<dfs(N,V);
	return 0;
}

代码提交状态: Time Limit Exceeded

上一篇:acwing 895. 最长上升子序列


下一篇:acwing数论笔记