背包问题算法

⑴ 背包问题C++递归算算法（求出所有解）

#include <fstream>
#include <vector>
#include <algorithm>
#include <time>
#include <queue>
#include <string>

using namespace std;

ofstream cout("out.txt");

struct Item
{
int v, w;
int x;
Item(int val = 0, int weight = 1, int sel = 0): v(val), w(weight), x(sel) {}
};

bool operator<(const Item& a, const Item& b)
{
return double(a.v) / a.w < double(b.v) / b.w;
}

struct Node
{
unsigned level;
int val;

int B;
int cv, cw;

Node *parent, *lson, *rson;
Node(int L, int V, Node* p):
level(L), val(V), parent(p), lson(0), rson(0) {}
};

class KnapsackBase
{
protected:
vector<Item> Items;
int Cap;
int MaxV;

int cw, cv; // for later use.
Node *Root; // as above.
int nNodes; // counting nodes.
string method;

int SumV(Node *p);
int SumW(Node *p);
int SumW();
float Bound(unsigned i);
void StoreX(Node *p);
void Print();
void DeleteTree(Node* r);
public:
KnapsackBase(const vector<Item>& items, int c):
Items(items), Cap(c)
{
sort(Items.begin(), Items.end(), not2(less<Item>()));
Root = new Node(0, -1, 0);
method = "Greedy";
}
virtual void Pack();
~KnapsackBase()
{
cout << "Destructing " << hex << this << dec << "; ";
nNodes = 0;
DeleteTree(Root);
cout << nNodes << " nodes deleted. -- " + method << endl;
}
};

float KnapsackBase::Bound(unsigned i)
{
int cleft = Cap - cw;
float b = cv;
while (i < Items.size() && Items[i].w <= cleft)
{
cleft -= Items[i].w;
b += Items[i].v;
i++;
}
if (i < Items.size())
b += (float(Items[i].v) / Items[i].w) * cleft;
return b;
}

void KnapsackBase::Pack()
{
unsigned i = 0;
int w = 0;
MaxV = 0;
while (i < Items.size())
{
if (Items[i].w + w <= Cap)
{
Items[i].x = 1;
w += Items[i].w;
MaxV += Items[i].v;
}
else
Items[i].x = 0;
i++;
}
Print();
}

void KnapsackBase::DeleteTree(Node* r)
{
if (r != 0)
{
DeleteTree(r->lson);
DeleteTree(r->rson);
delete r;
nNodes++;
}
}

int KnapsackBase::SumV(Node *p)
{
int s = 0;
while (p != Root)
{
s += Items[p->level - 1].v * p->val;
p = p->parent;
}
return s;
}

int KnapsackBase::SumW(Node *p)
{
int s = 0;
while (p != Root)
{
s += Items[p->level - 1].w * p->val;
p = p->parent;
}
return s;
}

void KnapsackBase::StoreX(Node *p)
{
for (unsigned i = Items.size() - 1; p != Root; p = p->parent, i--)
Items[i].x = p->val;
}

int KnapsackBase::SumW()
{
int s = 0;
for (unsigned i = 0; i < Items.size(); i++)
s += Items[i].w * Items[i].x;
return s;
}

void KnapsackBase::Print()
{
cout << "Result of " + method + " at " << hex << this << dec << endl;
for (unsigned i = 0; i < Items.size(); i++)
cout << Items[i].v << "\t" << Items[i].w << "\t" << Items[i].x << endl;
cout << MaxV << "\t" << SumW() << endl;
}

//----------------------------------------------------------------------------
class KnapsackDFS: public KnapsackBase
{
void DFS(Node* r);
public:
KnapsackDFS(const vector<Item>& items, int c): KnapsackBase(items, c)
{
method = "DFS";
}
void Pack()
{
MaxV = 0;
DFS(Root);
Print();
}
};

void KnapsackDFS::DFS(Node* r)
{
if (r->level == Items.size())
{
int V = SumV(r);
int W = SumW(r);
if (W <= Cap && V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
r->lson = new Node(r->level + 1, 0, r);
DFS(r->lson);
r->rson = new Node(r->level + 1, 1, r);
DFS(r->rson);
}
}

//----------------------------------------------------------------------------
class KnapsackBFS: public KnapsackBase
{
void BFS();
public:
KnapsackBFS(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "BFS";}
void Pack()
{
MaxV = 0;
BFS();
Print();
}
};

void KnapsackBFS::BFS()
{
queue<Node*> Q;
Node* r;
Q.push(Root);
while (!Q.empty())
{
r = Q.front();
Q.pop();
if (r->level == Items.size())
{
int V = SumV(r);
int W = SumW(r);
if (W <= Cap && V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
r->lson = new Node(r->level + 1, 0, r);
Q.push(r->lson);
r->rson = new Node(r->level + 1, 1, r);
Q.push(r->rson);
}
}
}

//----------------------------------------------------------------------------
class KnapsackBacktrack: public KnapsackBase
{
void Backtrack(Node* r);
public:
KnapsackBacktrack(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "Backtrack";}
void Pack()
{
MaxV = 0;
cw = 0;
cv = 0;
Backtrack(Root);
Print();
}
};

void KnapsackBacktrack::Backtrack(Node* r)
{
if (r->level == Items.size())
{
int V = SumV(r);
if (V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
if (cw + Items[r->level].w <= Cap)
{
r->rson = new Node(r->level + 1, 1, r);
cv += Items[r->level].v;
cw += Items[r->level].w;
Backtrack(r->rson);
cv -= Items[r->level].v;
cw -= Items[r->level].w;
}
if (Bound(r->level + 1) > MaxV)
{
r->lson = new Node(r->level + 1, 0, r);
Backtrack(r->lson);
}
}
}

//----------------------------------------------------------------------------
class KnapsackFIFOBB: public KnapsackBase
{
void FIFOBB();
public:
KnapsackFIFOBB(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "FIFOBB";}
void Pack()
{
MaxV = 0;
cv = 0;
cw = 0;
FIFOBB();
Print();

}
};

void KnapsackFIFOBB::FIFOBB()
{
queue<Node*> Q;
Node* r;
Root->cv = 0;
Root->cw = 0;
Q.push(Root);
while (!Q.empty())
{
r = Q.front();
Q.pop();
if (r->level == Items.size())
{
int V = SumV(r);
if (V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
if (r->cw + Items[r->level].w <= Cap)
{
r->rson = new Node(r->level + 1, 1, r);
r->rson->cv = r->cv + Items[r->level].v;
r->rson->cw = r->cw + Items[r->level].w;
Q.push(r->rson);
}

cv = r->cv;
cw = r->cw;
if (Bound(r->level + 1) > MaxV)
{
r->lson = new Node(r->level + 1, 0, r);
r->lson->cv = r->cv;
r->lson->cw = r->cw;
Q.push(r->lson);
}
}
}
}

//----------------------------------------------------------------------------
class KnapsackLCBB: public KnapsackBase
{
void LCBB();
public:
KnapsackLCBB(const vector<Item>& items, int c): KnapsackBase(items, c) {method = "LCBB";}
void Pack()
{
MaxV = 0;
cv = 0;
cw = 0;
LCBB();
Print();

}
};

class Compare
{
public:
Compare(){}
bool operator()(const Node *p, const Node *q)
{
if (p->B == q->B)
return p->level < q->level;
else
return p->B < q->B;
}
};

void KnapsackLCBB::LCBB()
{
priority_queue<Node*, vector<Node*>, Compare> Q;
Node* r;
Root->cv = 0;
Root->cw = 0;
Root->B = Bound(0);
Q.push(Root);
while (!Q.empty())
{
r = Q.top();
Q.pop();
if (r->level == Items.size())
{
int V = SumV(r);
int W = SumW(r);
if (W <= Cap && V > MaxV)
{
StoreX(r);
MaxV = V;
}
}
else
{
if (r->cw + Items[r->level].w <= Cap)
{
r->rson = new Node(r->level + 1, 1, r);
r->rson->cv = r->cv + Items[r->level].v;
r->rson->cw = r->cw + Items[r->level].w;
r->rson->B = r->B;
Q.push(r->rson);
}

cv = r->cv;
cw = r->cw;
int b;
if ((b = Bound(r->level + 1)) > MaxV)
{
r->lson = new Node(r->level + 1, 0, r);
r->lson->cv = r->cv;
r->lson->cw = r->cw;
r->lson->B = b;
Q.push(r->lson);
}
}
}
}

//----------------------------------------------------------------------------
void test()
{
const int N = 10;
vector<Item> A(N);
for (unsigned i = 0; i < N; i++)
{
A[i].v = 10 + rand() % 20;
A[i].w = 5 + rand() % 25;
}

KnapsackBase B(A, 100);
B.Pack();
cout << endl;

KnapsackDFS E(A, 100);
E.Pack();
cout << endl;

KnapsackBFS R(A, 100);
R.Pack();
cout << endl;

KnapsackBacktrack T(A, 100);
T.Pack();
cout << endl;

KnapsackFIFOBB F(A, 100);
F.Pack();
cout << endl;

KnapsackLCBB C(A, 100);
C.Pack();
cout << endl;
}

int main()
{
time_t t;
srand((unsigned) time(&t));

test();

return 0;
}

⑵ C语言 背包问题 递归算法

if(n==0)应该改成

if(n<0)才对，表示没有物品可选了。我的一个改进，但输出选择项还是有问题！

#include<stdio.h>
#include<conio.h>
#defineN3
intMaxW(intn,intC,int*Volume,int*Weight,int*Select){
intW=0,W1=0;
if(n<0){//没有物品了
return0;
}
W=MaxW(n-1,C,Volume,Weight,Select);//没放入n之前的重量
if(C>=Volume[n]){//背包剩余空间可以放下物品n
W1=MaxW(n-1,C-Volume[n],Volume,Weight,Select)+Weight[n];//放入n所能得到的重量
Select[n]=0;
if(W1>W){//放入n能获得更大的重量
Select[n]=1;
W=W1;
}
}
returnW;
}

intmain(){
intC=8,W,i;
//intVolume[N]={1,2,3,4,5};//物品体积
//intWeight[N]={1,2,5,7,8};//物品重量
intVolume[N]={2,3,5};//物品体积
intWeight[N]={5,8,7};//物品重量
intSelect[N]={0};//选择标记
W=MaxW(N-1,C,Volume,Weight,Select);
printf("MaxWeight=%d,SelectList[index(volume,weight)]:
",W);
for(i=0;i<N;++i){
if(Select[i]){
printf("%d(%d,%d)",i,Volume[i],Weight[i]);
}
}
printf("
Finished!
");
getch();
return0;
}

其中的Select数组还是会多选了，你看看。

⑶ C语言背包问题递归算法

你学过数据结构了吗？如果学过，那就比较好理解，该算法的思路和求二叉树的高度的算法的思路是十分类似的。把取这i个物体看成i个阶段，则该二叉树有i+1层。其中空背包时为根结点，左孩子则为放弃了第1个物品后的背包，右孩子为选取了第1个物品后的背包。今后在对第i个物品进行选择时，向左表示放弃，向右表示选取。则递归算法可如下：
int fun(int s, int i, int n) //s传入的是背包容量, i是进行第i个物品的选取，n为剩余物品的件数
{
if(s == 0) return 有解；
else if(剩余的每件物品都装不进|| n == 0) return 无解；
L = fun(s, i + 1, n - 1); //放弃第i个物品，则下一步的背包容量仍为s，然后看其是否有解，(递归调用进入左子树)
R = fun(s - wi, i + 1, n - 1); //选取第i个物品，则下一步的背包容量为s-wi，然后看其是否有解，(递归调用进入右子树)
return (l, r); //综合考虑左右两边，看哪边是正解或都无解。其实应该返回 return (L||R);
}

⑷ 用贪心算法求解背包问题的最优解。

你这个是部分背包么？也就是说物品可以随意分割？
那么可以先算出单位重量物品的价值，然后只要从高价值到低价值放入就行了，按p[i]/w[i]降序排序，然后一件一件加，加满为止！
贪心的思路是：加最少的重量得到更大的价值！
算出单位价值为{6,4,3,2,7,5,2}
加的顺序即为5,1,6,2,3,4/7
如果重量不超过就全部都加，超过就加满为止
不懂可问望采纳！
推荐看dd_engi的背包九讲，神级背包教程！在此膜拜dd_engi神牛~

⑸ 急，分全拿出来了，算法中的背包问题的贪心算法

#include <stdio.h>
#include <iostream.h>

#define MAXWEIGHT 20
#define n 3

float pw[n]={0},x[n]={0};
int w[n]={0},p[n]={0};

void sort(int p[],int w[])
{
int temp1,temp2;
float temp;
int i,j;
for(i=0;i<n;i++)
{
pw[i]=float(p[i])/w[i];
}

for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pw[i]<pw[j])
{
temp=pw[i],pw[i]=pw[j],pw[j]=temp;
temp1=p[i],temp2=w[i];
p[i]=p[j],w[i]=w[j];
p[j]=temp1,w[j]=temp2;
}
}

}

}

void GreedyKnapsack(int p[],int w[])
{
int m=MAXWEIGHT,i;
for(i=0;i<n;i++) x[i]=0.0;
for(i=0;i<n;i++)
{
if(w[i]>m) break;
x[i]=1.0;
m=m-w[i];
}
if(i<n) x[i]=float(m)/w[i];

}

void main()
{
int i;
printf("请输入每个物体的效益和重量:\n");
for(i=0;i<n;i++)
{
cin>>p[i]>>w[i];
}
for(i=0;i<n;i++)
{
printf("原物体%d的效益和重量分别为%d,%d:\n",i+1,p[i],w[i]);
}
sort(p,w);
printf("\n\n\n按效益值非递增顺序排列物体:\n");
for(i=0;i<n;i++)
{
printf("物体%d的效益和重量分别为%d,%d 效益值为:%f\n",(i+1),p[i],w[i],pw[i]);

}
GreedyKnapsack(p,w);
printf("\n\n\n最优解为:\n");
for(i=0;i<n;i++)
{
printf("第%d个物体要放%f:\n",i+1,x[i]);
}

}

这是正确的算法

⑹ 背包问题的贪心算法C＋＋

为啥不用动态规划呢？
背包的贪心法是每次都选择收益最大，如果包还能容纳，就放入包里面，并把这个物品去掉。

⑺ 背包问题的问法变化

以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，在这里值得提一下。但是我认为，只要深入理解了求背包问题最大价值的方法，即使问法变化了，也是不难想出算法的。
例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（f数组）之后得到。
还有，如果要求的是“总价值最小”“总件数最小”，只需简单的将上面的状态转移方程中的max改成min即可。
下面说一些变化更大的问法。 一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。
还是以01背包为例，方程为f[v]=max{f[v],f[v-c]+w}。再用一个数组g [v]，设g[v]=0表示推出f[v]的值时是采用了方程的前一项（也即f[v]=f[v]），g[v]表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品。那么输出方案的伪代码可以这样写（设最终状态为f[N][V]）：
i=N
v=V
while(i>0)
if(g[v]==0)
print 未选第i项物品
else if(g[v]==1）
print 选了第i项物品
v=v-c
另外，采用方程的前一项或后一项也可以在输出方案的过程中根据f[v]的值实时地求出来，也即不须纪录g数组，将上述代码中的g [v]==0改成f[v]==f[v]，g[v]==1改成f[v]==f[v-c]+w也可。
输出字典序最小的最优方案
这里“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。
一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为v-c[1]，物品为2..N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2..N的子问题。不管答案怎样，子问题的物品都是以i..N而非前所述的1..i的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。
在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[v]==f及f[v]==f[f-c]+w同时成立，应该按照后者（即选择了物品i）来输出方案。 对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是01背包中的物品，转移方程即为f[v]=sum{f[v],f[v-c]+w}，初始条件f[0][0]=1。
事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。 这里的最优方案是指物品总价值最大的方案。还是以01背包为例。
结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：f[v]意义同前述，g[v]表示这个子问题的最优方案的总数，则在求f[v]的同时求g[v]的伪代码如下：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c]+w}
g[v]=0
if(f[v]==f[v])
inc(g[v],g[v]
if(f[v]==f[v-c]+w)
inc(g[v],g[v-c])
如果你是第一次看到这样的问题，请仔细体会上面的伪代码。 显然，这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域（例如数论、图论）结合起来的问题，在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程，遇到其它的变形问法，只要题目难度还属于NOIP，应该也不难想出算法。
触类旁通、举一反三，应该也是一个OIer应有的品质吧。

⑻ 求背包问题贪心算法实例结果

找零钱问题：以人民币1元，2元，5元，10元，20元，50元，100元为例，要求所找的张数最少
背包问题：假设物体重量W1，W2．．．Wn其对应的价值为P1，P2．．．Pn，物体可分割，求装入重量限制为m的背包中的物体价值最大．可用P/W来解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的结构体
{
double p;//价值
double w;//重量
double r;//价值与重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品个数
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心
scanf("%lf",&m);//读入包的容量m
s=0;//包内现存货品的重量
value=0;//包内现存货品总价值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//输出结果
return 0;
}

⑼ 0-1背包问题用什么实现算法最好

我们书上给的0-1背包问题是是用动态规划方法做的这个算法是动态规划的典型应用所以你把动态规划的思想搞清楚就应该可以理解了下面我把动态规划的思想给你说一下,希望对你有所帮助.哦..不好意思..时间不多了..你自己到网上找一下这方面的思想..然后结合一个实例认真研读一下..弄懂之后..你对动态规划..0-1背包问题就会有比较深入的理解.建议好好学一下算法..这对计算机专业学生来说很重要..我越来越觉得祝学有所成

⑽ 求完全背包问题的代码(C语言或C++版)或算法

背包问题小结- []2006-07-28

做到背包问题觉得很有意思，写写看看。
完全背包问题可以用贪心算法。
代码如下：

program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;

procere choose;
var i,j:integer;

begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;

begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];

close(input);
choose;
writeln(x:5:2);
end.
编得不是很好 ^-^ 献丑了。

我来说说0/1背包问题。
状态：当前物品n
算符：j=0（当前物品不放入背包） 或 j=1（当前物品放入背包）
这就很好说了，还是把yes函数一改，问题OK了。
代码如下：

program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始数据}
s:array[1..maxn] of integer;{当前的状态}
r:array[1..maxn] of integer;{当前的总质量}
m:integer;{背包容量}
max:integer;{物品个数}
procere try(n:integer);
var j:integer;

{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}

begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最优解}end
end else
begin
if r[n-1]>m then exit;{已超过背包总容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;

begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.

用yes 函数要从头到当前求已装入背包物品的总质量，时间效率不高。所以我们引入r[n]数组来记录当前背包总质量（很好用！）注意用r[n-1]>m来做剪枝，以再次提高时间效率。

DC跟我说可以用二进制解此类问题。我觉得很有创意，也说说。比如8个物品，每个物品有0/1两种状态所以我们从(00000000)(二进制 )到（11111111）（二进制）循环即可。然后在分离十进制数对应起来即可。但在实际的操作中发现效率比回溯还低，我想有两方面的原因：1、显而易见，不可能做剪枝。2、每一次结果都要从1到8求和十效率降低。不过这确实是一种很新颖的算法。