# 11013: 【原1013】无限背包

### 题目描述

author: 韩立 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1013

## Input Format

$$V \leq 10000, N \leq 1000$$。

## Sample Input

5 3
2 3
3 2
4 1


## Sample Output

6


## FineArtz's solution

#include <iostream>
#include <map>
using namespace std;

int main(){
map<int, int> bucket;
int f[10005] = {0};
int v, n;
cin >> v >> n;
while (n--){
int vi, wi;
cin >> vi >> wi;
if (bucket.find(vi) != bucket.end()){
if (bucket[vi] < wi) bucket[vi] = wi;
}
else bucket[vi] = wi;
}
for (auto i = bucket.begin(); i != bucket.end(); ++i)
for (int j = i->first; j <= v; ++j)
f[j] = max(f[j], f[j - i->first] + i->second);
cout << f[v] << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"
using namespace std;
int weight[1009] = { 0 }, value[1009] = { 0 },dp_data[10009] = { 0 };
int dp(int v, int n) {
if (dp_data[v] > 0) return dp_data[v];
int ans = 0;
for (int i = 0; i < n; ++i)
if (weight[i] <= v) {
auto temp = dp(v - weight[i], n) + value[i];
ans = temp > ans ? temp : ans;
}
dp_data[v] = ans;
return ans;
}
int main() {
int v, n;
cin >> v >> n;
for (int i = 0; i < n; ++i)
cin >> weight[i] >> value[i];
cout << dp(v, n);
return 0;
}


## yyong119's solution

#include <iostream>
int w[1001],v[1001],f[10001];
int n,m,i,j,k;
int main(){
using namespace std;
cin>>m>>n;
for (i=1; i<=n; i++) cin>>w[i]>>v[i];
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
if ((i-w[j]>=0)&&(f[i]<f[i-w[j]]+v[j])) f[i]=f[i-w[j]]+v[j];
cout<<f[m];
return 0;
}