/**
 * POJ probem 3624: 0/1 knapsack algorithm
 * Basically, use brute force search method (dfs).
 * A better way is to use DP.
 *
 * hellfire (asyncloading#163.com)
 * Jan 31th, 2016
 */

#include<iostream>

using namespace std;

int n;

int m;

int martix[12880][2];
int mem[3402][12880];

int dfs(int i, int j)
{
  int res;
  if (mem[i][j] >= 0)
  {
    return mem[i][j];
  }
  if (i == n)
  {
    res = 0;
  }
  else if (martix[i][0] > j )
  {
    res = dfs(i + 1, j);
  }
  else 
  {
    res = max(dfs(i + 1, j), dfs(i + 1, j - martix[i][0]) + martix[i][1]);
  }
  return mem[i][j] = res;
}

int main(int argc, char **argv)
{
  cin >> n >> m;
  int k;
  for (k = 0; k < n; k ++)
  {
    cin >> martix[k][0] >> martix[k][1];
  }
  memset(mem, -1, sizeof(mem));
  int result = dfs(0, m);
  cout << result << endl;
}

• Re:尼玛啊。。。用记忆搜索，二维数组，结果内存爆掉了。。 (981) GSMU 2016-03-09 17:27:46
• Re:尼玛啊。。。用记忆搜索，二维数组，结果内存爆掉了。。你得用一唯的 (981) GSMU 2016-03-09 17:28:06