这是一个递归求解背包问题的算法,我的运行结果有错,求指点和改正我的程序
/* 这个程序正确结果应为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;
}