| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 445 人关注过本帖
标题:这是一个递归求解背包问题的算法,我的运行结果有错,求指点和改正我的程序
只看楼主 加入收藏
chenbin1991x
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2012-11-1
结帖率:0
收藏
已结贴  问题点数:20 回复次数:2 
这是一个递归求解背包问题的算法,我的运行结果有错,求指点和改正我的程序
/* 这个程序正确结果应为1190,而程序运行结果为1000,求指点。*/
/*背包问题求解*/
#include "stdafx.h"
#include<iostream>  
using namespace std;  
      
const int W= 100;      
const int number = 5;  
const int VALUE[] = {80, 190, 100, 700, 1000};  
const int WEIGHT[] = {10, 30, 50, 60, 70};  

//function Make( i {处理到第i件物品} , j{剩余的空间为j}) :integer;  
int Make(int i, int j)  
{   
    int r1 = 0;  
    int r2 = 0;  
    int r=0;
   
    if (i == -1)  
    {  
        return 0;  
    }  
      
    if(j >= WEIGHT[i])   //背包剩余空间可以放下物品 i   
    {  
        r1 = Make(i-1,j - WEIGHT[i]) + VALUE[i]; //第i件物品放入所能得到的价值  
        r2 = Make(i-1,j); //第i件物品不放所能得到的价值   
        r = (r1>r2)?r1:r2;  
    }     
      
    return r;  
}

int main(int argc, char* argv[])
{
    printf("Hello World!\n");
    int maxValue = Make(number-1, W);  
    cout<<"maxValue: "<<maxValue<<endl;  
    return 0;
}

搜索更多相关主题的帖子: include return function 
2012-11-01 21:55
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:20 
Ding ~
2012-11-02 20:23
chenbin1991x
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2012-11-1
收藏
得分:0 

其实这个问题后来我问过同学了:只要在return r;之前加一句 else r=make(i-1,w)即可,运行正确了。
2012-12-17 09:10
快速回复:这是一个递归求解背包问题的算法,我的运行结果有错,求指点和改正我的 ...
数据加载中...
 
   



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

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