动态规划01背包问题关于状态转移方程。
下面是网上普通递归的一部分代码,我的疑问是:max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i])这个式子,它一层层递归下去,计算机为什么能自己判断所有情况中的最优,我还没学算法表述不好,就是一句话 它这个递归的过程是怎么去一步步运作的,好奇这个max(。。。)怎么可以检索出最优的情况呢??望大牛解答。程序代码:
#include <stdio.h> #include <tchar.h> #include <queue> #include "iostream" using namespace std; const int N = 4; const int W = 5; int weight[N] = {2, 1, 3, 2}; int value[N] = {3, 2, 4, 2}; int record[N][W]; void init() { for(int i = 0; i < N; i ++) { for(int j = 0; j < W; j ++) { record[i][j] = -1; } } } int solve(int i, int residue) { if(-1 != record[i][residue]) return record[i][residue]; int result = 0; if(i >= N) return result; if(weight[i] > residue) { record[i + 1][residue] = solve(i+1, residue); } else { result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]); } return record[i + 1][residue] = result; } int main() { init(); int result = solve(0, W); cout << result << endl; return 0; }