如何通过迭代解决0-1包问题？
可能的重复：
将递归算法转换为迭代算法的设计模式 < /p>
只能想出一个递归的方法： 如何将其转化为迭代？ 为了简单起见，我的递归方式只找到结果值。
#include<iostream>
//0-1 bag
using namespace std;
int weight[5]={50,30,45,25,5};
int value[5]={200,180,225,200,50};
int valueAfterTake(int objectNO, int bagSpaceLeft)
{
int take,notTake;
if(objectNO < 0)
{
return 0;
}
else
{
take = value[objectNO] + valueAfterTake(objectNO - 1,bagSpaceLeft - weight[objectNO]);
notTake = valueAfterTake(objectNO - 1, bagSpaceLeft);
}
if(weight[objectNO] > bagSpaceLeft)
{
return notTake;
}
if(take > notTake)
{
return take;
}
else
{
return notTake;
}
}
int main()
{
cout<<valueAfterTake(4,100)<<endl;
return 0;
}
Possible Duplicate:
Design patterns for converting recursive algorithms to iterative ones
I can only figure out a recursive way:
how to transform it into iteration?
for simplicity, my recursive way only find the result value.
#include<iostream>
//0-1 bag
using namespace std;
int weight[5]={50,30,45,25,5};
int value[5]={200,180,225,200,50};
int valueAfterTake(int objectNO, int bagSpaceLeft)
{
int take,notTake;
if(objectNO < 0)
{
return 0;
}
else
{
take = value[objectNO] + valueAfterTake(objectNO - 1,bagSpaceLeft - weight[objectNO]);
notTake = valueAfterTake(objectNO - 1, bagSpaceLeft);
}
if(weight[objectNO] > bagSpaceLeft)
{
return notTake;
}
if(take > notTake)
{
return take;
}
else
{
return notTake;
}
}
int main()
{
cout<<valueAfterTake(4,100)<<endl;
return 0;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
鉴于您真正想要的，我认为这是 的重复问题将递归算法转换为迭代算法的设计模式
Given what you really want, I think this is a duplicate question of Design patterns for converting recursive algorithms to iterative ones
从0-1背包问题中的算法可以将所有内容放入i和w的表中。< br>
制作一个二维表，其中填充 NO_VALUE 常量（-1 或类似的值）。
然后，当您需要获取 m[i, w] 的值时，您可以从表中找到所需的索引，检查它们是否已计算（通过与 NO_VALUE 进行比较），如果没有则计算它们。
在这里，您将在空间权衡中获得更少的代码执行，因为您永远不会两次计算相同的值。
编辑：
此外，从那里您可以继续查找模式，就像您总是使用一行或一条对角线等，然后剪掉表格中不需要的所有内容。
From the algorithm in 0-1 knapsack problem can put everything in a table of i and w.
Make a two diminutional table filled with NO_VALUE constants(-1 or something like that).
Then when you need to get the value for m[i, w] you find what indexes from the table you need, check if their computed(by comparing to NO_VALUE), and computing them if their not.
Here you will gain much less code execution in tradeoff for space because you will never compute the same value twice.
edit:
In addition, from there you can continue to find patterns, like you're always using one row, or one diagonal and such and cut out everything you don't need in the table.