Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:尼玛啊。。。用记忆搜索，二维数组，结果内存爆掉了。。

Posted by GSMU at 2016-03-09 17:27:46 on Problem 3624
In Reply To:尼玛啊。。。用记忆搜索，二维数组，结果内存爆掉了。。 Posted by:hellfiresong at 2016-01-31 11:35:03
```> /**
>  * POJ probem 3624: 0/1 knapsack algorithm
>  * Basically, use brute force search method (dfs).
>  * A better way is to use DP.
>  *
>  * 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;
> }
```

Followed by: