# 背包问题解决器

**Repository Path**: lin-yimian/backpack-problem-solver

## Basic Information

- **Project Name**: 背包问题解决器
- **Description**: 借助网页可视化展示，探讨使用动态规划和分支限界方法解决0-1背包问题的适用场景
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2025-01-19
- **Last Updated**: 2025-09-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 背包问题解决器



### 介绍
借助网页可视化展示，探讨使用动态规划和分支限界方法解决0-1背包问题的适用场景

### 软件架构  
前端：
考虑到实际情况以及更好的满足用户交互性需求，系统采用可视化的前端界面来允许用户进行商品的选购，用户可以通过就如同在淘宝京东等购物平台购物的方式，点击商品将其加入到待选择清单，选择完毕后就能够提交包含自己想要选择的商品数组以及预算等信息的表单，后端在处理完前端提供的数据后就能返回方案。
后端：
考虑到跨服务器的问题，虽然前端提交的json数据能够正常提交以JAVA语言开发的Web接口上，但在不同服务器上的运行会涉及到一定的跨域问题。基于本项目体量小的特点，并不需要把问题复杂化，算法的实现可以就在本地服务器，计算完成后直接返回到界面上进行渲染，从而保证了执行效率以及稳定性。


### 系统运行结果以及相关结论   
影响动态规划算法规模的是物品数量以及预算，其数值越大，二维数组的规模就越大，相应的时空复杂度也会上升。
而对于分支限界法，其时间复杂度波动很大，随着物品数量的增加，呈现了指数倍的上涨，而且它一定程度上依赖于减枝逻辑，选择了好的减枝策略，可以极大缩短时空复杂度

#### 预算的影响   
如果我们选择很少的金额以致东西很多无法购买的，
由于预算少，在动态规划中，二维数组的列数少，很快的就可以将二维数组呈现出来，整个算法只进行了8次的比较；
反观分支限界法，虽然金额很少，往往在一开始就会因为价格超支而被减去，但是由于需要遍历所有物品的情况，选择用时上仍然很高 。
在这种情况下，使用动态规划法的时间复杂度是最为理想的。

如果考虑到更为极端的情况，比如说预算极其充足，所有物品可以购买，
那么这个时候背包问题就有不利之处了，可以看到它的时间复杂度和空间复杂度都是很高的，甚至在表格中都无法完全呈现，可想而知他的冗余操作非常多的；
而看到分支限界法，虽然选择用时也不少，但是在这种余额远超于所选物品价格总和的情况之下，相较于动态规划还是有优势的，而这个优势在物品越少的时候体现的越明显。
 

当然这个情况不太实际，既然有了极其充足的预算，所有东西都能购买就不必考虑选择哪一些了。为了证明分支限界算法在现实中的优势，我们设立一个情况，那就是预算并不能购买所有的商品，但是原因并不是预算太少，而是商品的价格比较高。
二维数组仍然出现了超时，因为虽然并不是所有东西都能够购买，但是由于二维数组仍然很多列，在时间复杂度上仍然很高，这显然不是我们所希望的。
而对于分支限界法，他从物品本身出发，对于一个30块钱的物品，它不需要如同动态规划一样考虑31，32，他只需要考虑要不要把这个物品放到背包里面，因此它在时间复杂度上仍然比较简单


#### 总结  
对于01背包，我们选择算法的标准有两个，一个是物品的数量，另一个则是在动态规划算法下我们背包重量递增所需要的列数，在物品数量越少，而列数越多的情况下，我们优先考虑分支限法，反之则是动态规划。  
还有一点值得注意的是分支限界法有上限，在所有物品都可以选取以后它的时间复杂度是不会变化的，但是动态规划算法的时间复杂度则会呈现持久的增长。