金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特……继续阅读 » 水墨上仙 8年前 (2017-06-09) 2454浏览 1559个赞
C语言回溯法解决背包问题#include #include #include using namespace std;#define MAXN 10struct Goods_Info{ int v; //价值 int w; //重量 double vw; //价值重量比}goods[MAXN];int n;……继续阅读 » 水墨上仙 8年前 (2017-05-31) 1651浏览 333个赞
0-1背包问题:给定n种物品和一背包.物品i的重量是wi, 其价值为ui,背包的容量为C. 问如何选择装入背包的物品,使得装入背包中物品的总价值最大? 分析: 0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题. 第一步 确定解空间：装入哪几种物品 第二步 确定易于搜索的解空间结构： 可以用数组p,w分别表示各个物品价值和重量。 用数组x记录，是否……继续阅读 » 水墨上仙 8年前 (2017-05-31) 2167浏览 2605个赞
