算法 | 用贪心求解背包&动态规划、回溯、分支限界法求解0-1背包
背包问题
普通背包:
贪心时间复杂度:O(nlogn)
首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心 选择策略,将尽可能多的单位重量价值最高的物品装入背包。若 将这种物品全部装入背包后,背包内的物品总重量未超过C,则选 择单位重量价值次高的物品并尽可能多地装入背包。依此策略一 直地进行下去,直到背包装满为止
//program 2.3 背包问题
#include
#include
using namespace std;
const int M=10005;
struct node{
double w;//每个物品的重量
double v;//每个物品的价值
double p;//性价比
}s[M];
bool cmp(node a,node b){//自定义比较函数
return a.p>b.p;//根据物品的单位价值从大到小排序
}
double solve(int n,double W){
double sum=0.0;//sum表示示装入物品的价值之和
double cleft=W;//背包剩余容量
for(int i=0;i<n;i++){//贪心算法求解
if(s[i].w>t;
while(t--){
cin>>n>>W;
for(int i=0;i>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;//每个宝物单位价值
}
sort(s,s+n,cmp);
cout<<solve(n,W)<<endl;//输出装入宝物的最大价值
}
return 0;
}
分别用动态规划法、回溯法、分支限界法设计 0-1背包问题
动态规划法时间复杂度:O(nc) c是背包容量。
这是因为需要填写一个二维数组来记录子问题的解。
//program 4.8 01背包
#include
#include
using namespace std;
const int maxn=105;
const int maxw=10005;
int c[maxn][maxw];//c[i][j]表示前i个物品放入容量为j的背包获得的最大价值
int w[maxn],v[maxn];//w[i]表示第i个物品的重量,v[i]表示第i个物品的价值
bool x[maxn]; //x[i]表示第i个物品是否放入背包
int knapsack(int n,int W){
for(int i=1;i<=n;i++){//计算c[i][j]
for(int j=1;j<=W;j++){
if(j0;i--){
if(c[i][j]>c[i-1][j]){
x[i]=1;
j-=w[i];
}
else
x[i]=0;
}
cout<<"装入背包的物品序号为:";
for(int i=1;i<=n;i++){
if(x[i])
cout<<i<<" ";
}
cout<>t;
while(t--){
cin>>n>>W;
for(int i=1;i>w[i]>>v[i];
for(int i=1;i<=n;i++)//初始化第0列为0
c[i][0]=0;
for(int j=1;j<=W;j++)//初始化第0行为0
c[0][j]=0;
cout<<knapsack(n,W)<<endl;
//print(n,W);
}
return 0;
}
/*测试数据
2
5 10
2 6
5 3
4 5
2 4
3 6
4 52
12 13
10 24
22 13
9 24
*/
回溯法O(2的n次方)
//program 5.2 01背包
#include
#include
using namespace std;
const int maxn=105;
int n; //物品数量
double W; //背包容量
double w[maxn],v[maxn];//w[i]表示第i个物品的重量,v[i]表示第i个物品的价值
double cw,cp,bestp; //当前重量,当前价值,最优值
bool x[maxn]; //x[i]表示第i个物品是否放入背包
bool bestx[maxn]; //最优解
double bound(int i){//计算上界(已装入物品价值+剩余物品(第i~n种物品)的总价值)
double rp=0;
while(in){//到达叶子
for(int j=1;j<=n;j++)//记录最优解
bestx[j]=x[j];
bestp=cp;//记录最优值
return ;
}
if(cw+w[t]bestp){//如果满足限界条件,搜索右子树
x[t]=0;
backtrack(t+1);
}
}
int knapsack(){
cw=0.0,cp=0.0,bestp=0.0; //当前放入背包的物品重量,价值,最优值
backtrack(1);
cout<<bestp<<endl;
// for(int i=1;i<=n;i++){ //输出最优解
// if(bestx[i]==1)
// cout<<i<<" ";
// }
// cout<>t;
while(t--){
cin>>n>>W;
for(int i=1;i>w[i]>>v[i];
knapsack();
}
return 0;
}
/*测试数据
2
5 10
2 6
5 3
4 5
2 4
3 6
4 52
12 13
10 24
22 13
9 24
*/
分支限界法时间复杂度接近于O(2^n)
//program 6.2 01背包 普通队列bfs AC 831ms
#include
#include
using namespace std;
const int maxn=105;
int n; //物品数量
double W; //背包容量
double w[maxn],v[maxn];//w[i]表示第i个物品的重量,v[i]表示第i个物品的价值
double bestp,sumv; //当前重量,当前价值,最优值,总价值
bool bestx[maxn]; //最优解
struct node{
double cp,rp; //cp当前放入背包的物品价值,rp剩余物品的价值
double rw; //剩余容量
int id; //物品号
node() {}
node(double _cp,double _rp,double _rw,int _id){
cp=_cp;
rp=_rp;
rw=_rw;
id=_id;
}
};
void knapsack_bfs(){
queue q; //创建一个普通队列(先进先出)
q.push(node(0,sumv,W,1)); //根结点入队
while(!q.empty()){ //如果队列不空
node cur,lc,rc;//定义三个结点型变量
cur=q.front();//取出队头元素
q.pop(); //队头元素出队
// cout<<cur.cp<<" "<<cur.rp<<" "<<cur.rw<<" "<<cur.id<n) continue;
if(cur.cp+cur.rp<bestp) continue;
int cp=cur.cp;
int rp=cur.rp-v[t];
if(w[t]bestp)//比最优值大更新
bestp=lc.cp;
q.push(lc);//左孩子入队
}
if(cp+rp>bestp){//满足限界条件
rc=node(cp,rp,cur.rw,t+1);//生成右孩子
q.push(rc);//右孩子入队
}
}
}
int main(){
int t;//t表示测试用例数
cin>>t;
while(t--){
cin>>n>>W;
bestp=0.0,sumv=0.0; //sumv为所有物品的总价值
for(int i=1;i>w[i]>>v[i];
sumv+=v[i];
}
knapsack_bfs();
cout<<bestp<<endl;
}
return 0;
}
/*测试数据
1
4 10
2 6
5 3
4 5
2 4
*/