範例程式碼 uva11003
//uva11003
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 1005
#define MAX_W 3005
using namespace std;
struct Box {
int weight;
int capacity;
};
Box boxes[MAX_N];
int n, dp[MAX_N][MAX_W];
int recurse(int capacity, int i);
int main() {
while (cin >> n) {
if (n == 0)
return 0;
for (int i = 0; i < n; i++)
cin >> boxes[i].weight >> boxes[i].capacity;
memset(dp, -1, sizeof(dp));
int lmax = 1;
for (int i = 0; i < n; i++) {
lmax = max(recurse(boxes[i].capacity, i + 1) + 1, lmax);
}
cout << lmax << endl;
}
}
int recurse(int capacity, int i) {
if (i == n || !capacity)
return 0;
int &memo = dp[i][capacity];
if (memo != -1)
return memo;
if (boxes[i].weight <= capacity)
return memo = max(recurse(min(capacity - boxes[i].weight, boxes[i].capacity), i + 1) + 1,recurse(capacity, i + 1));
else
return memo = recurse(capacity, i + 1);
}