注册 登录
编程论坛 数据结构与算法

这是一个递归求解背包问题的算法,我的运行结果有错,求指点和改正我的程序

chenbin1991x 发布于 2012-11-01 21:55, 445 次点击
/* 这个程序正确结果应为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;
}

2 回复
#2
寒风中的细雨2012-11-02 20:23
Ding ~
#3
chenbin1991x2012-12-17 09:10

其实这个问题后来我问过同学了:只要在return r;之前加一句 else r=make(i-1,w)即可,运行正确了。
1