#include<iostream>
using namespace std;
int best_solution(int i,int c,int values[],int weights[])//i表示拿入几个商品，c表示容量
{
if (i == 0 || c == 0)return 0;//递归出口
if (weights[i] > c)return best_solution(i - 1, c, values, weights);//容量太大，舍弃
//放得下，需要考虑是否放下能得到最大
int tmp1 = best_solution(i - 1, c, values, weights);//不放
int tmp2 = best_solution(i - 1, c - weights[i], values, weights) + values[i];
int result = tmp1>tmp2?tmp1:tmp2;
return result;
}
void best_solution2(int bestarr[5][11], int values[], int weight[])
{
for (int i = 0; i < 5; i++){bestarr[i][0] = 0;}
for (int i = 0; i < 11; i++) { bestarr[0][i] = 0; }
for (int i = 1; i < 5; i++)
{
for (int j = 1; j < 11; j++)
{
if (j < weight[i])//容量够
bestarr[i][j] = bestarr[i - 1][j];
else
{
if (bestarr[i - 1][j] > bestarr[i - 1][j - weight[i]] + values[i])
{
bestarr[i][j] = bestarr[i - 1][j];
}
else
{
bestarr[i][j] = bestarr[i - 1][j - weight[i]] + values[i];
}
}
}
}
}
void print(int best_s[5][11])
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 11; j++)
{
cout << " " << best_s[i][j];
}
cout << endl;
}
}
int main(int* argc, int* argv[])
{
int values[5] = { 0,2,4,3,7 };
int weights[5] = { 0,2,3,5,5 };
int result = best_solution(4,10, values, weights);
cout << result << endl;
int best_s[5][11];
best_solution2(best_s, values, weights);
print(best_s);
}
0-1背包问题——递归与动态规划
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 继续讲故事~~ 转眼我们的主人公丁丁就要离开自己的家乡，去大城市见世面了。这天晚上，妈妈正在耐心地帮丁丁收拾...
