文章目录
- 一、题目
- 二、功能模块图
- 三、问题分析
- 四、实验结果及分析
- 五、源码
- 总结
一、题目 【数据结构|背包问题求解（数据结构课设）】?背包问题的求解:假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：
（1，4，3，2）
（1，4，5）
（8，2）
（3，5，2）。
二、功能模块图
文章图片
三、问题分析 按照问题描述
1.处理好数据读入 。
2.再分别标记背包剩余容量，即当前处理到的物品i，用栈存储需 要放进书包里的物品。
3.在循环里处理数据，当判断到处理完毕，用 break 退出循环。先判断物品能否放入背包，能则压进栈，然后判断剩余容量是否为 0，若为 0，输出结果，并且使栈和i为下一情况，若不为0，则通过进一步判断决i的值和栈的状态。
四、实验结果及分析 背包问题求解：输入测试样，并得出解。与书中测试结果一致。由此判断完成题目要求。
文章图片
另外还存在以下几种无解情况，当背包体积过大，或物品体积过大时均无解，如下所示。
文章图片
五、源码 main.cpp
#include
#include
#include
#define max 1000
using namespace std;
int main() {
// read the datas
int T, n;
int W[max];
bool found = false;
cout << "请输入背包大小: ";
cin >> T;
cout <> n;
cout <> W[j];
cout << endl << "解有 : " << endl;
// process
int left = T;
stack s;
int i = 0;
while (1) {
if (left == W[i] || (left > W[i] && i < n)) {// 可以放进背包的情况
s.push(i);
left -= W[i];
}if (left == 0) {// 刚好装满
// 标记
found = true;
// 输出结果
stack t;
while (!s.empty()) {
t.push( s.top());
s.pop();
}
cout << "( ";
while (!t.empty()) {
cout << W[t.top()] << " ";
s.push(t.top());
t.pop();
}
cout << ")" < 总结 此为本人2022年大二下学期数据结构课设中的一道题目。特此记录。
推荐阅读
- 2021年高教社杯全国大学生数学建模竞赛题目 C题 思路方法
- mysql|Mysql高级学习笔记
- 数据结构|教学计划编制问题（数据结构课程设计）
- java|【华为OD机试真题 JAVA】用连续自然数之和来表达整数
- 面试|分布式大全（反向代理/Redis/中间件/MySQL/消息，挑战阿里P7必备）
- java|刷透近200道数据结构与算法，成功加冕“题王”，挤进梦中的字节
- java|阿里力荐（这本Java性能调优实战，MySQL+JVM+Tomcat问题迎刃而解）
- 面试|阿里言（出乎意料，“字节跳动”居然是这么做数据迁移的）
- java|阿里大数据面试题集合（Hadoop+HBase+Spark+Zookeeper）