C语言算法求助:假设有这么一组物品,其大小和价值如下表所示:物品编号\x05大小\x05价值1\x05 2\x0532\x05 3\x0523\x05 4\x0534\x05 5\x0575\x05 6\x059\x05给一个容量为16的背包,设计算法求解价值最大的组
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/24 20:55:38
C语言算法求助:假设有这么一组物品,其大小和价值如下表所示:物品编号\x05大小\x05价值1\x05 2\x0532\x05 3\x0523\x05 4\x0534\x05 5\x0575\x05 6\x059\x05给一个容量为16的背包,设计算法求解价值最大的组
C语言算法求助:
假设有这么一组物品,其大小和价值如下表所示:
物品编号\x05大小\x05价值
1\x05 2\x053
2\x05 3\x052
3\x05 4\x053
4\x05 5\x057
5\x05 6\x059
\x05给一个容量为16的背包,设计算法求解价值最大的组合.
用C或C++编写 感激不尽!
C语言算法求助:假设有这么一组物品,其大小和价值如下表所示:物品编号\x05大小\x05价值1\x05 2\x0532\x05 3\x0523\x05 4\x0534\x05 5\x0575\x05 6\x059\x05给一个容量为16的背包,设计算法求解价值最大的组
//如果每种商品只有一件,是0-1背包问题 读入的数据N代表物品个数 V代表背包容量.
//对于你的例子 ,输入为
//5 16
//2 3
//3 2
//4 3
//5 7
//6 9
//输出为21
#include
using namespace std;
#define MAXSIZE 1000
int f[MAXSIZE + 1],c[MAXSIZE + 1],w[MAXSIZE + 1];
int main()
{
int N,V;
cin >> N >> V;
int i = 1;
for (; i > c[i] >> w[i];
}
for (i = 1; i = c[i]; --v) //c[i]可优化为bound,bound = max {V - sum c[i,...n],c[i]}
{
f[v] = (f[v] > f[v - c[i]] + w[i] f[v] :f[v - c[i]] + w[i]);
}
}
//当i=N时,可以跳出循环单独计算F[V]
cout