背包问题中背包的体积都很小，就像此题，背包体积不超过 1000，但如果背包体积很大，达到 $1\times10^9$ 以上，又该如何解决问题？

我尝试用记忆化搜索和 map 解决，但是效率好像并不高。

#include<iostream>
#include<map>
using namespace std;
int n,W;
const int MAX_SIZE=100;
int w[MAX_SIZE+1],v[MAX_SIZE+1];
map<pair<int,int>,int>record;
int rec(int i,int j){
	if(record.find({i,j})==record.end()){
		int res;
		if(i==n)res=0;
		else if(j<w[i])res=rec(i+1,j);
		else res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
		record[{i,j}]=res; 
	}
	return record[{i,j}];
}
int main(){
	scanf("%d%d",&W,&n);
	for(int i=0;i<n;i++)scanf("%d%d",w+i,v+i);
	printf("%d",rec(0,W));
}