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

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

Posted by hellfiresong at 2016-01-31 11:35:03 on Problem 3624
```/**
* 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:

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