| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3641 人关注过本帖
标题:动态规划01背包问题关于状态转移方程。
只看楼主 加入收藏
我叫K
Rank: 2
等 级:论坛游民
帖 子:74
专家分:19
注 册:2015-4-28
结帖率:90.91%
收藏
 问题点数:0 回复次数:3 
动态规划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;  
}  
搜索更多相关主题的帖子: 计算机 color 背包 动态 网上 
2015-08-07 13:07
我叫K
Rank: 2
等 级:论坛游民
帖 子:74
专家分:19
注 册:2015-4-28
收藏
得分:0 
我还没学算法,不过对max(。。。)部分有疑问,为什么通过这样子能找出最优化的情况。max中它一层层递归下去,每一次递归都是选或者不选,所有的情况它会去记录下来??有劳前辈给我解下惑了

他们和我说,喜欢一个女生要大胆追!
2015-08-07 13:42
Bett
Rank: 1
等 级:新手上路
帖 子:15
专家分:9
注 册:2015-8-17
收藏
得分:0 
max(a,b)是常用函数库中的一个比较函数,自动返回a,b中较大的一个赋值。
2015-08-20 16:34
醒山
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:9
帖 子:463
专家分:2071
注 册:2015-5-25
收藏
得分:0 
你的程序不能运行吧,max你没有包含头文件,也没有自己定义max函数

[ 本帖最后由 醒山 于 2015-8-25 15:17 编辑 ]
2015-08-25 15:03
快速回复:动态规划01背包问题关于状态转移方程。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016702 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved