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

Re:尼玛啊。。。用记忆搜索,二维数组,结果内存爆掉了。。你得用一唯的

Posted by GSMU at 2016-03-09 17:28:06 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.
>  *
>  * 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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator