2020-05-22
所有背包问题实现的例子都是下面这张图
01背包实现之——穷举法：
1.我的难点：
（1）在用穷举法实现代码的时候，我自己做的时候认为最难的就是怎么将那么多种情况表示出来，一开开始想用for循环进行多次嵌套，但是太麻烦，而且还需要不断的进行各种标记。我现在的水平实在太菜，然后就在一篇博文中看到一个特别巧妙的枚举算法,如下所示：
int fun(int x[n])
{
int i;
for(i=0;i<n;i++)
if(x[i]!=1) {x[i]=1; return;}
//从遇到的第一位开始，若是0，将其变成1，然后结束for循环，得到一种解法
else x[i]=0;
return;
//从第一位开始，若是1，将其变成0，然后继续循环，若再循环的时候遇到0，则将其变为1，结束循环。得到另一种解法。
}
虽然我现在也不知道为什么会这样，但是确实是个很好的规律，找到这个规律后，就可以很轻松的自己写出各种排列情况，以后遇到排列的问题，就用这个方法。语言不好描述，上图片演示（是歪的，凑活看吧。。。）：
（2）算法思想：
x[i]的值为0/1，即选或者不选
w[i]的值表示商品i的重量
v[i]的值表示商品的价值
所以这个算法最核心的公式就是
tw=x[1]*w[1]+x[2]*w[2]+.......+x[n]*w[n]
tv=x[1]*w[1]+x[2]*v[2]+......+x[n]*v[n]
tv1:用于存储当前最优解
limit:背包容量
如果 tw<limit&&tv>tv1 则可以找到最优解
2.代码实现（借鉴博文）
#include<stdio.h>
#include<iostream>
using namespace std;
#define n 4
void possible_solution(int x[n]){
int i;
for(i=0;i<4;i++) //n=4,有2^4-1种解法
if(x[i]!=1)
{
x[i]=1;
return; //从遇到的第一位开始，若是0，将其变成1，然后结束循环，得到一种解法
}
else
x[i]=0;
return;//从第一位开始，若是1，将其变成0，然后继续循环，若再循环的时候遇到0，则将其变为1，结束循环。得到另一种解法。
}
int main(){
int count=0;
int w[n]={2,3,4,5},v[n]={3,4,5,6};
int x[n]={0,0,0,0},y[n]={0,0,0,0};
int tw,tv,tv1=0,limit=8;
int j;
for(j=1;j<=15;j++){
possible_solution(x);
count++;
for(int i=0;i<4;i++){
cout<<x[i]<<" ";
}
cout<<endl;
tw=x[0]*w[0]+x[1]*w[1]+x[2]*w[2]+x[3]*w[3];
tv=x[0]*v[0]+x[1]*v[1]+x[2]*v[2]+x[3]*v[3];
if(tw<=limit&&tv>tv1){
tv1=tv; y[0]=x[0];y[1]=x[1];y[2]=x[2],y[3]=x[3];
}
}
cout<<"共有"<<count<<"种解法."<<endl;
printf("其中0-1背包问题的最优解为： y=(%d,%d,%d,%d)\n",y[0],y[1],y[2],y[3]);
printf("总价值为：%d",tv1);
}
3.运行结果：
4.复杂度分析
n个物品的话，就有2^n-1种解，所以其时间复杂度为O(2^n)
01背包问题之——贪心算法：
1.算法思路：
取单位价值量最大的那个物品先装入背包。所以还算好实现，得到每一个物品的价值量之后，查找最大的价值量的坐标，判断这个坐标额物品体积是否小于背包的容量，若小于，则装入背包。否则，继续循环。
2.代码实现 法一：
将得到的每个物品的价值量进行排序，得到一个递减序列。
#include<iostream>
#include <iomanip>
#define n 4 //物品数列
#define c 8 //背包容量
using namespace std;
int w[4]={2.0,3.0,4.0,5.0};
float v[4]={3.0,4.0,5.0,6.0};
float sortBest[4]; //v[i]/w[i]
int C(){
for(int i=0;i<4;i++){
sortBest[i]=v[i]/w[i];
//cout<<sortBest[i]<<" ";
}
cout<<endl;
}
int Sort(){
for(int i=0;i<4;i++)
{
int temp;
int wtemp;
int vtemp;
if(sortBest[i+1]>sortBest[i])
{
temp=sortBest[i];
sortBest[i]=sortBest[i+1];
sortBest[i+1]=temp;
wtemp=w[i];
w[i]=w[i+1];
w[i+1]=wtemp;
vtemp=v[i];
v[i]=v[i+1];
v[i+1]=vtemp;
}
//用来查看排序是否正确
cout<<"w["<<i<<"]="<<w[i]<<" ";
cout<<endl;
cout<<"v["<<i<<"]="<<v[i]<<" ";
cout<<endl;
cout<<"sortBest["<<i<<"]="<<sortBest[i]<<endl;
}
cout<<endl;
}
int F(){
int c1=c;
int result=0;
for(int i=0;i<4;i++){
if(w[i]<=c1)
result=result+v[i];
c1=c1-w[i];
}
cout<<"最优值是："<<result;
}
int main()
{
C();
cout<<"背包重量是："<<c<<endl;
Sort();
F();
return 0;
}
代码实现 法二：
没有对每个商品的价值量进行排序，直接查找当前价值量的最大值，判断其是否能够装入背包，若能，直接装入，令当前价值量为0，继续寻找第二大价值量，不断循环即可。代码如下：
#include<iostream>
#include <iomanip>
#define n 4 //物品数列
#define c 8 //背包容量
using namespace std;
float w[4]={2.0,3.0,4.0,5.0};
float v[4]={3.0,4.0,5.0,6.0};
float sortBest[4]; //价值量 v[i]/w[i]
int C(){
for(int i=0;i<4;i++){
sortBest[i]=v[i]/w[i];
//cout<<sortBest[i]<<" ";
}
}
int F()
{
float temp=0;
float result=0;
float c1=8; //用于改变c的值
for(int i=0;i<4;i++)
{
//for循环用来得到最大sortBest
for(i=0;i<4;i++)
{
if(temp<sortBest[i])
temp=sortBest[i];
}
//cout<<"max(sortBest)="<<temp<<endl;
for(i=0;i<4;i++)
{
if (temp==sortBest[i])
//cout<<"最大sortBest的下标是："<<i<<endl;
sortBest[i]=0;
if (w[i]<=c1)
result=result+v[i];
c1=c1-w[i];
}
}
cout<<"结果为："<<result<<endl;
}
int main()
{
cout<<"********贪心算法解决01背包问题,谁的sortBest=v[i]/w[i] 大，就先拿谁***********"<<endl;
cout<<"背包的总重量是:"<<c<<endl;
cout<<"可挑选的物品共4件"<<endl;
cout<<endl;
for(int i=0;i<4;i++)
{
cout<<"w["<<i<<"]="<<w[i]<<" ";
cout<<"v["<<i<<"]="<<v[i]<<" ";
cout<<"sortBest["<<i<<"]="<<v[i]/w[i]<<" ";
cout<<endl;
}
C();
F();
return 0;
}
3.遇到的困难
就是，当得到的价值量的包含小数时，而且刚好就靠小数部分区分大小时（比如1.5 ，1.33，）。c++正常输出的结果都是整数。
解决办法就是，将每个物品的价值量（3.0,4.0）和背包重量（2.0,3.0）都变float类型，注意定义的时候，也需要定义为float类型
4.复杂度：
时间复杂度：O(n)
01背包问题之——动态规划
表如何填写不再介绍，都是来源于递推公式，
1.算法思想
最重要的就是寻找递推关系式：
定义V[i,j]:当背包容量为j时，前i个物品最佳组合对应的值。
递推关系：
（1）当背包的容量不允许装入第i件物品时，和前一个物品装入背包一样。即 ：V[i][j]=V[i-1][j]
（2）当背包的容积可以装入第i件物品时，分两种情况，A装入第i件物品不是最优，还不如不装。B装入第i件物品是最优。即:V[i][j]=max(V[i-1][j],V[i][j-w[i]]+v[i])
2.代码实现：
#include<iostream>
using namespace std;
int w[5]={0,2,3,4,5};
int v[5]={0,3,4,5,6};
int V[5][9];
int c=8;
int B()
{
int i,j;
for(i=0;i<5;i++)
{
V[i][0]=0;
for(j=0;j<c+1;j++)
{
V[0][j]=0;
if(j<w[i])
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
}
}
}
int main(){
B();
//显示填好的表格
for (int i=0;i<5;i++)
{
for(int j=0;j<9;j++)
{
cout<<V[i][j]<<" ";
}
cout<<endl;
}
cout<<"最优结果是："<<V[4][8];
return 0;
}
下面是带上回溯找出解的组成的代码：
#include<iostream>
using namespace std;
int w[5]={0,2,3,4,5};
int v[5]={0,3,4,5,6};
int V[5][9];
int c=8;
int item[4];
int B()
{
int i,j;
for(i=0;i<5;i++)
{
V[i][0]=0;
for(j=0;j<c+1;j++)
{
V[0][j]=0;
if(j<w[i])
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
}
}
}
void FindWhat(int i,int j)//寻找解的组成方式
{
if(i>=0)
{
if(V[i][j]==V[i-1][j])//相等说明没装
{
item[i]=0;//全局变量，标记未被选中
FindWhat(i-1,j);
}
else if( j-w[i]>=0 && V[i][j]==V[i-1][j-w[i]]+v[i] )
{
item[i]=1;//标记已被选中
FindWhat(i-1,j-w[i]);//回到装包之前的位置
}
}
}
int main(){
B();
//显示填好的表格
cout<<"得到的表格如下图所示："<<endl;
for (int i=0;i<5;i++)
{
for(int j=0;j<9;j++)
{
cout<<V[i][j]<<" ";
}
cout<<endl;
}
cout<<"最优结果是："<<V[4][8]<<endl;
FindWhat(4,8);
cout<<endl;
cout<<"回溯得到的解是："<<endl;
for(int i=1;i<5;i++){
if(item[i]==1)
cout<<"背包里面有第"<<i<<"号物品"<<endl;
//cout<<item[i]<<" ";
}
return 0;
}
贴上结果便于理解：
3.复杂度
时间复杂度：
O(物体个数*背包容积)=O(number*capacity)
空间复杂度：
用二维表实现的，所以和时间复杂度一样。
O(物体个数*背包容积)=O(number*capacity)
01背包之——递归
01背包之——回溯
原文：https://www.cnblogs.com/zhaoxiansheng666/p/12939259.html