一,算法策略应用
1)关于背包问题
按与利润关系划分
•与利润无关的背包问题
•与利润有关的背包问题
按物体装入背包的多少
•部分背包问题
•0-1背包问题
2)背包问题的求解策略,根据不同的需求
•贪心法、回溯法、分支限界法、动态规划
• 递归或非递归求解
二,背包问题展示
1)背包问题1
•
问题描述:给定n种物品,从中选出m件,使其重量之和与T之差的绝对值为最小。
例如:n=9,m=3,T=500克。
• 问题分析1:采用三重循环,枚举法。
数据变化过程:
(1,2,3) (1,2,4) …(1,2,9)
(1,3,4) (1,3,5) …(1,3,9)…(1,8,9)
(2,3,4) (2,3,5) …(2,3,9) … (7,8,9)
• 算法1分析 时间复杂度为O(n3)
•
源码:
#include <iostream>
using namespace std;
int main()
{
int a[9]={1,2,3,4,5,6,7,8,9};
int m=3;
int T=5;
int diff;
int mindiff=999;
int tempi,tempj,tempk;
for(int i=0;i<9;++i)
{
for(int j=i+1;j<9;++j)
{
for(int k=j+1;k<9;++k)
{
diff=(a[i]+a[j]+a[k]-T>0?a[i]+a[j]+a[k]-T:T-(a[i]+a[j]+a[k]));
if(mindiff>diff)
{
mindiff=diff;
tempi=i;
tempj=j;
tempk=k;
}
}
}
}
cout<<"select number is:"<<a[tempi]<<" "<<a[tempj]<<" "<<a[tempk]<<endl;
cout<<"Sunm :"<<a[tempi]+a[tempj]+a[tempk]<<endl;
cout<<"mindiff: "<<mindiff<<endl;
}
2)背包问题2
•
问题描述:给定n种物品和一重量为M背包。物品i的重量是wi。问应如何选择装入背包的物品,使得装入背包中物品的总重量为最重。找出问题的所有解。例如,当M=10,各件物品分别为{5,2,3.5,1.7,1,5.1}。
•问题分析2:采用多重循环,枚举法。
• 源码:
#include <iostream>
using namespace std;
int main()
{
double a[6]={5,2,3.5,1.7,1,5.1};
double M=10;
double max=0;
double temp;
for(int i1=0;i1<=1;++i1)
{
for(int i2=0;i2<=1;++i2)
{
for(int i3=0;i3<=1;++i3)
{
for(int i4=0;i4<=1;++i4)
{
for(int i5=0;i5<=1;++i5)
{
for(int i6=0;i6<=1;++i6)
{
temp=a[0]*i1+a[1]*i2+a[2]*i3+a[3]*i4+a[4]*i5+a[5]*i6;
if(temp<=M&&max<temp)
max=temp;
}
}
}
}
}
}
cout<<max<<endl;
}
改进:可以采用将十进制,转为二进制。例如000001 表示只选一个,000011表示选两个。循环次数为2`6
3)背包问题3
•
问题描述:给定n种物品和一重量为M背包。物品i的重量是wi。问应如何选择装入背包的物品,使得装入背包中物品的总重量恰好为M,找出问题的所有解。例如,当M=10,各件物品分别为{1,8,4,3,5,2},可得到4组解(1,4,3,2)(1,4,5)(8,2)(3,5,2)
• 问题分析
利用回溯法,逐个试探将物品依次放入背包,若超过背包的重量,则弃之当前所选物品,继续选下一个,如此重复,直至找出所有的解,或无解。
假设对物品序列{1,8,4,3,5,2}编号为1、2、3、4、5、6,此问题中物品取出的顺序和装入的顺序正好相反,考虑可使用栈来描述求解。
• 源码
#include <iostream>
#include <stack>
using namespace std;
int w[6]={1,8,4,3,5,2};
int M=10;
void StackTraverse(stack<int> S)
{
cout<<"这一组结果是:"<<endl;
while(!S.empty())
{
cout<<w[S.top()]<<endl;
S.pop();
}
}
void knapsack(int w[],int M, int n)
{
stack<int> S;
int k=0; //从第1件物品考察
while(!S.empty()||k<n)
{
while(M>0&&k<n)
{
if(M-w[k]>=0)
{
S.push(k);
M-=w[k];
}
k++;
}
if (M==0)
StackTraverse(S); //输出一组解,继续求下一组解
k=S.top()+1;//下一个继续
M+=w[S.top()];//恢复M值
S.pop();//弹出最上边的,回溯
}
}
int main()
{
knapsack(w,M,6);
return 0;
}
4)背包问题4--利润背包问题的贪心算法
•
问题描述:给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为M。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
• 贪心性质分析
每次从物品集中选择单价最高的物体,如果其重量小于背包所余重量,就可把它放入背包。然后我们就面临了一个最优子问题——它同样是一个背包问题,只不过这时的总容量M减少了,物品集减小了。因此,背包问题也明显具有最优子结构性质。我们可以用贪心算法求解。
• 用贪心法解背包问题4的基本步骤
(1)先计算每种物品单位重量的价值pi/wi;
(2)如果n种物品的总重量小于总重量M,则只需要全部放入背包就可以。
(3)否则,依据物品单位重量价值,从很高到低装入背包。
(4)若背包内的物品总重量未超过M,依此策略一直地进行下去,直到背包装满为止。
(5)最后装入的可能是物品的一部分。
5)背包问题5 –0-1背包问题的动态规划法
问题描述:给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为M。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?(不允许物品拆零)详细参见博文http://blog.csdn.net/tianshuai11/article/details/7533317
6)背包问题6––0-1背包问题的分支限界法
•问题描述:给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为M。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?(不允许物品拆零),并给出所装物品的方案的队列式分支限界法。
• 算法分析
算法的计算时间上界为 O(2`n )
•对于0-1背包问题,贪心选择之所以不能得到最优解是因为它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。
• 事实上,在考虑0-1背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。由此导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征
分享到:
相关推荐
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
背包问题.本算法比较清晰,易读。运行后自动出结果。 背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的...
基于双子群协同进化思想和果蝇优化算法,...通过对多个0-1背包问题的算例进行测试,并将测试结果与其他文献结果进行比较,结果表明,双子群果蝇优化算法具有较好的全局寻优能力,可作为求解0-1背包问题的一种实用方法。
0-1背包问题 0-1背包问题 0-1背包问题 0-1背包问题
回溯算法解0--1背包问题
算法与设计课程设计,0-1背包,背包问题,棋盘覆盖问题
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
关于背包问题的源代码,包括贪心算法和动态算法
算法-动态规划- 背包问题 P04- 混合背包(包含源程序).rar
分发分析与设计里面的0-1背包问题 分发分析与设计里面的0-1背包问题 分发分析与设计里面的0-1背包问题 分发分析与设计里面的0-1背包问题
基于智能优化算法的控制器优化设计终稿 - 副本.docx基于智能优化算法的控制器优化设计终稿 - 副本.docx基于智能优化算法的控制器优化设计终稿 - 副本.docx基于智能优化算法的控制器优化设计终稿 - 副本.docx基于智能...
0-1背包问题-算法简洁易懂
0-1-背包问题与遗传算法 使用遗传算法在 Python 中解决 0-1 背包问题的简单方法
C++ 0-1背包问题源码 算法分析与设计代码的完善 算法复习必备
0-1背包问题问题,使用的回溯算法来实现了。挺简单的实现。
使用遗传算法解决0-1背包问题,调试成功,非常适合初学者了解遗传算法和0-1背包问题
遗传算法与优化问题 遗传算法与优化问题 遗传算法与优化问题
算法设计与分析、课程设计报告、普通背包、棋盘覆盖
这是一个很好的解决贪心算法背包问题非0-1背包问题的算法。
算法设计,0-1背包问题,用java编写的贪心算法实现0-1背包问题。。