C语言算法求助:假设有这么一组物品,其大小和价值如下表所示:物品编号\x05大小\x05价值1\x05 2\x0532\x05 3\x0523\x05 4\x0534\x05 5\x0575\x05 6\x059\x05给一个容量为16的背包,设计算法求解价值最大的组
来源:学生作业帮助网 编辑:作业帮 时间:2024/09/01 12:49:14
![C语言算法求助:假设有这么一组物品,其大小和价值如下表所示:物品编号\x05大小\x05价值1\x05 2\x0532\x05 3\x0523\x05 4\x0534\x05 5\x0575\x05 6\x059\x05给一个容量为16的背包,设计算法求解价值最大的组](/uploads/image/z/5454162-18-2.jpg?t=C%E8%AF%AD%E8%A8%80%E7%AE%97%E6%B3%95%E6%B1%82%E5%8A%A9%EF%BC%9A%E5%81%87%E8%AE%BE%E6%9C%89%E8%BF%99%E4%B9%88%E4%B8%80%E7%BB%84%E7%89%A9%E5%93%81%2C%E5%85%B6%E5%A4%A7%E5%B0%8F%E5%92%8C%E4%BB%B7%E5%80%BC%E5%A6%82%E4%B8%8B%E8%A1%A8%E6%89%80%E7%A4%BA%EF%BC%9A%E7%89%A9%E5%93%81%E7%BC%96%E5%8F%B7%5Cx05%E5%A4%A7%E5%B0%8F%5Cx05%E4%BB%B7%E5%80%BC1%5Cx05+2%5Cx0532%5Cx05+3%5Cx0523%5Cx05+4%5Cx0534%5Cx05+5%5Cx0575%5Cx05+6%5Cx059%5Cx05%E7%BB%99%E4%B8%80%E4%B8%AA%E5%AE%B9%E9%87%8F%E4%B8%BA16%E7%9A%84%E8%83%8C%E5%8C%85%2C%E8%AE%BE%E8%AE%A1%E7%AE%97%E6%B3%95%E6%B1%82%E8%A7%A3%E4%BB%B7%E5%80%BC%E6%9C%80%E5%A4%A7%E7%9A%84%E7%BB%84)
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