完全背包
View Code #include#include #include #include #include using namespace std;#define maxm 50005#define maxn 15int n, m, y;int weight[maxn], value[maxn];int f[maxm];void input(){ scanf("%d%d", &m, &y); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", &weight[i], &value[i]); weight[i] /= 1000; }}int work(){ double x = m; for (int i = 0; i < y; i++) x *= 1.1; int temp = ceil(x) / 1000 + 2; memset(f, 0, sizeof(f)); for (int i = 0; i < n; i++) for (int j = weight[i]; j <= temp; j++) f[j] = max(f[j], f[j - weight[i]] + value[i]); int ret = m; for (int i = 0; i < y; i++) ret = ret + f[ret / 1000]; return ret;}int main(){ //freopen("t.txt", "r", stdin); int t; scanf("%d", &t); while (t--) { input(); printf("%d\n", work()); } return 0;}