导读：很多朋友问到关于python背包最多装多少重量的相关问题，本文首席CTO笔记就来为大家做个详细解答，供大家参考，希望对大家有所帮助！一起来看看吧！
0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法）
一.动态规划求解0-1背包问题
/************************************************************************/
/* 0-1背包问题：
/* 给定n种物品和一个背包
/* 物品i的重量为wi，其价值为vi
/* 背包的容量为c
/* 应如何选择装入背包的物品，使得装入背包中的物品
/* 的总价值最大？
/* 注：在选择装入背包的物品时，对物品i只有两种选择，
/* 即装入或不装入背包。不能将物品i装入多次，也
/* 不能只装入部分的物品i。
/*
/* 1. 0-1背包问题的形式化描述：
/* 给定c0, wi0, vi0, 0=i=n，要求找到一个n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且满足如下约束：
/* (1) sum_{i=1 to n} (wi*xi) = c
/* (2) xi∈{0, 1}, 1=i=n
/*
/* 2. 0-1背包问题的求解
/* 0-1背包问题具有最优子结构性质和子问题重叠性质，适于
/* 采用动态规划方法求解
/*
/* 2.1 最优子结构性质
/* 设(y1,y2,...,yn)是给定0-1背包问题的一个最优解，则必有
/* 结论，(y2,y3,...,yn)是如下子问题的一个最优解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) = c - w1*y1
/* (2) xi∈{0, 1}, 2=i=n
/* 因为如若不然，则该子问题存在一个最优解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最优解。那么有：
/* sum_{i=2 to n} (vi*zi) sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) = c
/* 进一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) = c
/* 这说明：(y1,z2,z3,...zn)是所给0-1背包问题的更优解，那么
/* 说明(y1,y2,...,yn)不是问题的最优解，与前提矛盾，所以最优
/* 子结构性质成立。
/*
/* 2.2 子问题重叠性质
/* 设所给0-1背包问题的子问题 P(i,j)为：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) = j
/* (2) xk∈{0, 1}, i=k=n
/* 问题P(i,j)是背包容量为j、可选物品为i,i+1,...,n时的子问题
/* 设m(i,j)是子问题P(i,j)的最优值，即最大总价值。则根据最优
/* 子结构性质，可以建立m(i,j)的递归式：
/* a. 递归初始 m(n,j)
/* //背包容量为j、可选物品只有n，若背包容量j大于物品n的
/* //重量，则直接装入；否则无法装入。
/* m(n,j) = vn, j=wn
/* m(n,j) = 0, 0=jwn
/* b. 递归式 m(i,j)
/* //背包容量为j、可选物品为i,i+1,...,n
/* //如果背包容量jwi，则根本装不进物品i，所以有：
/* m(i,j) = m(i+1,j), 0=jwi
/* //如果j=wi，则在不装物品i和装入物品i之间做出选择
/* 不装物品i的最优值：m(i+1,j)
/* 装入物品i的最优值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j=wi
/*
/************************************************************************/
#define max(a,b) (((a) (b)) ? (a) : (b))
#define min(a,b) (((a) (b)) ? (a) : (b))
template typename Type
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//递归初始条件
int jMax = min(w[n] - 1, c);
for (int j=0; j=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j=c; j++) {
m[n][j] = v[n];
}
//i从2到n-1，分别对j=wi和0=jwi即使m(i,j)
for (int i=n-1; i1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c = w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template typename Type
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; in; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; in+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsackint(v, w, c, n, ppm);
TraceBackint(ppm, w, c, n, x);
return 0;
}
二.贪心算法求解0-1背包问题
1.贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1).不能保证求得的最后解是最佳的；
2).不能用来求最大或最小解问题；
3).只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
2.例题分析
1).[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
程序代码:(环境:c++)
#includeiostream.h
#define max 100 //最多物品数
void sort (int n,float a[max],float b[max]) //按价值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k=n;k++)
c[k]=a[k]/b[k];
for(h=1;hn;h++)
for(j=1;j=n-h;j++)
if(c[j]c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1为背包剩余可装载重量
int i;
sort(n,v,w); //物品按价值密度排序
c1=limitw;
for(i=1;i=n;i++)
{
if(w[i]c1)break;
x[i]=1; //x[i]为1时，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout"请输入n和limitw:";
cinn limitw;
for(i=1;i=n;i++)
x[i]=0; //物品选择情况表初始化为0
cout"请依次输入物品的价值："endl;
for(i=1;i=n;i++)
cinv[i];
coutendl;
cout"请依次输入物品的重量："endl;
for(i=1;i=n;i++)
cinw[i];
coutendl;
knapsack (n,limitw,v,w,x);
cout"the selection is:";
for(i=1;i=n;i++)
{
coutx[i];
if(x[i]==1)
totalw=totalw+w[i];
}
coutendl;
cout"背包的总重量为："totalwendl; //背包所装载总重量
cout"背包的总价值为："totalvendl; //背包的总价值
}
三.回溯算法求解0-1背包问题
1.0-l背包问题是子集选取问题。
一般情况下，0-1背包问题是NP难题。0-1背包
问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类
似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当
右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余
物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右
子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后
依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是
右子树中解的上界。
2.解决办法思路：
为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考
察各物品即可。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
2.算法框架：
a.问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。
b.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
3.运用回溯法解题通常包含以下三个步骤：
a.针对所给问题，定义问题的解空间；
b.确定易于搜索的解空间结构；
c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
#includeiostream
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m=n;m++)
{
coutbestx[m]" ";
}
coutendl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解
};
int Knap::Bound(int i)
{
//计算上界
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i=nw[i]=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(in)
{
if(bestpcp)
{
for(int j=1;j=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]=c) //搜索左子树
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)bestp)//搜索右子树
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator=(Object a)const
{
return (d=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W=c)
return P;//装入所有物品
//依物品单位重量排序
float f;
for( i=0;in;i++)
for(int j=i;jn;j++)
{
if(Q[i].dQ[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout"0-1背包问题——回溯法 "endl;
cout" by zbqplayer "endl;
while(k)
{
cout"请输入背包容量(c)："endl;
cinc;
cout"请输入物品的个数(n)："endl;
cinn;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout"请输入物品的价值(p)："endl;
for(i=1;i=n;i++)
cinp[i];
cout"请输入物品的重量(w)："endl;
for(i=1;i=n;i++)
cinw[i];
cout"最优解为(bestx)："endl;
cout"最优值为(bestp)："endl;
coutKnapsack(p,w,c,n)endl;
cout"[s] 重新开始"endl;
cout"[q] 退出"endl;
cink;
}
四.分支限界法求解0-1背包问题
1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。
2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。
#include iostream.h
struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};
int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; inumber; i++)
{
cout"请输入第件"i+1"物品的重量:";
cinbag[i].weight;
cout"请输入第件"i+1"物品的效益:";
cinbag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
coutendl;
}
}
int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; numnumber (w+bag[num].weight)=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界
for(int i=0; inumber; i++)//逐层遍历解树决定是否装入各个物品
{
if( ( bound_c=getbound(i+1, bound_u) )upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志
if( getbound(i, bound_u)bound_c )//遍历右子树
//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}
}
void Display()
{
cout"可以放入背包的物品的编号为：";
for(int i=0; inumber; i++)
if(bag[i].flag0)
couti+1" ";
coutendl;
delete []bag;
}
Python贪婪算法之Python算法题实战 -《完美的代价》
最近也没什么事可做,就在备赛蓝桥杯(Python).蓝桥杯主要考察的是算法题目.所以我也在网上找了些资源刷题,昨天当我刷到《完美的代价》这道题目的时候,我就被卡住了.怎么想也想不通,就连解题代码也看不懂.更 搞笑 的是,昨天晚上我睡觉的时候,就在思考这道题目,结果不到一分钟,我就入睡了...
今天起床后,我就在CSDN里面找寻思路,有些博主提到,《完美的代价》需要用到贪心算法,但是我也没正经学过相关的算法,所以就去研究了一下贪心算法,发现这个算法还有点意思呢
贪心算法并不是一个具体的算法，而是一种算法的思想，或者说是解决问题的一种思路
要想弄明白贪心算法,可以从这两个关键点入手:
贪心算法最大的特点，就是在每一步中取最优化的解，不会回溯处理。这样的策略，自然在执行速度上更快，但是因为这种方法的短视。会导致得的解并不是真正的全局最优解，但是贪心算法得到的依然是一个近似最优解
问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高
通俗解释：假如你有一个只能承重100的背包，你往里面装一些重量和价值不等的东西，怎样才可以让你的背包中的价值最大
这个问题中就是关键在于，每个转入背包的东西，只能是被装入背包和不被装入背包两种状态，可以用0-1表示。所以叫0-1背包问题。其二，就是这个问题的两个限定。第一，背包的边界是明确，它只能承重那么多东西。第二，东西的边界是明确的，你只有那么一些东西可以选择
故而，这个问题其实有三种策略可以选择：
这三种策略中，策略一看起来最好的策略
但是，策略一的模糊化太大，需要根据特殊的情况，做出特殊的改变
策略二和策略三相同，本身上并没有太多不同。只是二者的视角不同
我们了解贪心算法后,再来看看这道算法题吧
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
第一行是一个整数N，表示接下来的字符串的长度(N
高分求python大神帮忙解答，实在有难度，做不出来
"""用itertools的组合工具combinations生成所有组合方案"""
import itertools
def sameSums(alst):
allsummary = sum(alst)
if allsummary % 2:
# 数组总和不能被2整除既不可均分为等值的两部分
return False
halfsum = allsummary / 2 # 总和的半值为检测目标
for l in xrange(1, len(alst)/2+1):
# 方案第一部分的数组长度从1位到数组半长
for sub in list(itertools.combinations(alst, l)):
# 按指定长度遍历组合方案
if sum(sub) == halfsum:
# 若当前方案的和为目标值则当前方案有效
# another为方案的第二部分数据列表
another = alst[:]
for x in sub:
another.pop(another.index(x))
print sub, tuple(another)
return True
return False
def optsamesum(alst):
"""优化一下"""
allsummary = sum(alst)
if allsummary % 2:
return False
halfsum = allsummary / 2
if max(alst) halfsum:
return False
sortedlst = sorted(alst)[::-1]
for l in xrange(1, len(alst)/2+1):
for sub in list(itertools.combinations(sortedlst, l)):
if sum(sub) halfsum:
break
if sum(sub) == halfsum:
another = sortedlst[:]
for x in sub:
another.pop(another.index(x))
print list(sub), another
return True
return False
if __name__ == "__main__":
sameSums([4, 7, 6, 3])
sameSums([3, 3])
sameSums([4, 12, 16])
sameSums([5, 1])
一般户外登山包 双肩背包超大容量旅行包65L 能承受多少公斤重量
分背包的品质而论。一般背到身上承受30-45公斤是没有问题的。再重不是背包能否承爱的问题，而且人能不能背得动的问题了！
想问下大神python的背包问题的源代码(最好玩也有伪代码，请用递归法实现)，因为只学过递归法，所
递归有层数限制，所以最好不要用，能不用就不用，没有想到什么好的算法，弄了个简单粗暴的，包容量除以最小质量的，就是最多可以装多少个，然后全排列一遍三种商品，并计算价值，取最大的一个价值，代码如下：
a, b, c = 2, 2.5, 3 # 三种商品质量
A, B, C = 4, 5, 6 # 三种商品价值
m = 100 # 包容量
ds = int(100 / min(a, b, c)) # 最小质量 取到最大数量
mx = 0 # 最大价值
nl = [] # 商品数量列表
for i1 in range(0, ds + 1): # 全排列
for i2 in range(0, ds + 1 - i1):
for i3 in range(0, ds + 1 - i1 - i2):
# 判断总质量 超出则舍弃
n = i1 * a + i2 * b + i3 * c
if n m:
continue
# 计算总价值 取最高值及排列并存储
j = i1 * A + i2 * B + i3 * C
if mx j:
mx = j
nl = [i1, i2, i3]
# 输出最大价值和组合
print(mx)
print(nl)
结语：以上就是首席CTO笔记为大家整理的关于python背包最多装多少重量的全部内容了，感谢您花时间阅读本站内容，希望对您有所帮助，更多关于python背包最多装多少重量的相关内容别忘了在本站进行查找喔。
以上内容为新媒号(sinv.com.cn)为大家提供！新媒号，坚持更新大家所需的互联网后端知识。希望您喜欢！
版权申明：新媒号所有作品（图文、音视频）均由用户自行上传分享，仅供网友学习交流，不声明或保证其内容的正确性，如发现本站有涉嫌抄袭侵权/违法违规的内容。请发送邮件至 k2#88.com(替换@) 举报，一经查实，本站将立刻删除。
