本文地址: http://blog.csdn.net/caroline_wendy
题目参考: http://blog.csdn.net/caroline_wendy/article/details/37912949
使用记忆化搜索, 需要存储每组的值, 下次不需要进行继续迭代, 可以降低至时间复杂度O(nW).
代码:
/* * main.cpp * * Created on: 2014.7.17 * Author: spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> #include <memory.h> #include <limits.h> #include <utility> #include <queue> #include <algorithm> using namespace std; class Program { static const int MAX_N = 100; int n=4, W=5; int w[MAX_N] = {2,1,3,2}, v[MAX_N]={3,2,4,2}; int dp[MAX_N+1][MAX_N+1]; int rec (int i, int j) { if (dp[i][j] >= 0) return dp[i][j]; int res; if (i==n) { res = 0; } else if (j<w[i]) { res = rec(i+1, j); } else { res = max(rec(i+1,j), rec(i+1, j-w[i])+v[i] ); } return dp[i][j] = res; } public: void solve() { memset(dp, -1, sizeof(dp)); printf("result = %d\n", rec(0, W)); } }; int main(void) { Program P; P.solve(); return 0; }
result = 7
编程算法 - 背包问题(记忆化搜索) 代码(C),布布扣,bubuko.com
原文:http://blog.csdn.net/caroline_wendy/article/details/37913341