若果把背包问题 直接按价值降序排列 和 按单位质量价值降序排列 两者的结果进行比较,能不能得出最优解?如果不能,在不涉及递归和穷举的前提下,有什么方法可以得出最优解?
3条回答 默认 最新
- lbcab 2016-05-19 04:42关注
选取价值最大者。反例:
W=30
物品:A B C
重量:28 12 12
价值:30 20 20
根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
选取单位重量价值最大的物品。反例:
W=30
物品:A B C
重量:28 20 10
价值:28 20 10
根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断.使用动态规划来处理背包问题:
背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。
Pi表示第i件物品的价值。参考代码:
#include <iostream> #include <vector> using namespace std; //物品类 class packitem{ public: packitem(int w, int v):weight(w), value(v){} int weight; int value; }; int matrix[5][10] = {0}; int maxValue(int matrix[][10], vector<packitem*> vecpack, int bagsize, int bagweight){ for(int i = bagsize - 1; i >= 0; --i){ for(int j = 0; j < bagweight; ++j){ packitem item = *vecpack[i]; if(item.weight > j + 1){ //当前背包不能装下此物品 if(0 == j){ matrix[i][j] = 0; } else{ matrix[i][j] = matrix[i + 1][j]; } } else{ int valueInbag = 0; if( i == bagsize - 1|| j - item.weight + 1 < 0){ matrix[i][j] = item.value; continue; } else{ int tmp = 0; if (j - item.weight >= 0) tmp = j - item.weight; valueInbag = matrix[i + 1][tmp] + item.value; matrix[i][j] = max(matrix[i + 1][j], valueInbag); } } } } for(int i = 0; i < bagsize; ++i){ for(int j = 0; j < bagweight; ++j){ cout<<matrix[i][j]<<" "; } cout<<endl; } return matrix[0][bagweight - 1]; } int main() { vector<packitem*> tmp; int w[] = {2,2,6,5,4}; int v[] = {6,3,5,4,6}; int bagweight = 10; for(int i = 0; i < 5; ++i){ tmp.push_back(new packitem(w[i], v[i])); } int result = maxValue(matrix, tmp, 5, bagweight); for(int i = 0; i < 5; ++i){ delete tmp[i]; } tmp.clear(); cout<<result<<endl; return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥50 有数据,怎么建立模型求影响全要素生产率的因素
- ¥50 有数据,怎么用matlab求全要素生产率
- ¥15 TI的insta-spin例程
- ¥15 完成下列问题完成下列问题
- ¥15 C#算法问题, 不知道怎么处理这个数据的转换
- ¥15 YoloV5 第三方库的版本对照问题
- ¥15 请完成下列相关问题!
- ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?
- ¥15 求daily translation(DT)偏差订正方法的代码
- ¥15 js调用html页面需要隐藏某个按钮