背包问题C++程序设计_百度知道背包问题是一个经典的算法问题，可以用动态规划，贪心法，分支界限法等方法解决
问题描述：有n个物品，编号1,2,3，、、n，其中第 i 个物品重量为Wi 价值 Vi ，有一个容量为W的背包。
在容量允许范围内，如何选择物品，可以得到最大的价值。（为了简单起见，假设物品的重量 Wi 和价值Vi 都是正数）
根据取物品的方式，背包问题又可以被分为三类：
0/1背包问题(0-1 knapsack problem)
这也是最常见的背包问题，对于每个物品，要么取走要么不取走，每个物品只能取一次。
可以用数学表达式表示为：
maximize& &
subject to&&
其中xi只能为1 或者0 &所以称为背包问题
有界限的背包问题(bounded knapsack problem)
对应于上文，每个物品最多可以取Gi次.也可以不取。用数学表达式描述为：
subject to&
注意看xi取值范围。其中的&界限&说的是取的次数上限
无界限背包(&unbounded knapsack problem&(UKP))
相应的，无界限背包说的就是每个物品取的次数无限了，也就是上文中的xi 可以为任意的正整数。
今天主要说的是0、1背包问题，解法是动态规划。当然，对于另外两种问题也会有所介绍。
问题分析：
用动态规划解问题首先要有效的找出子问题，可以通过这个子问题得推得原问题的解，通常子问题的实质是和原问题相同的，只是规模上的缩小，
也就是说子问题和原问题可以有相同的表示形式，问题可通过不断的缩小规模（一般都会有一个界限）能找到子问题的解。
这个问题要求解的是能用背包带走的物品的最大价值。定义&m[i,w] 为：
用第1,、2、3、、i 个物品装入质量&=W的背包的最大价值。
m[i,w]的取值情况分析：
1）& ，背包的质量为w，里面没有物品，所以它的价值为0；
2）& &，背包质量为0，所以里面没法装任何东西， 不论前面的 i 是多少，总价值为0；
对于任意的第 i &个物品，有两种情况，放进背包或者不放。
不要第 i &个物品 如果&则：
3）& & 因为第i 个物品的重量大于背包的容量，所以不可放入。
如果. 那么
对于第 i 个物品，有两种可选择方案：如果放入背包中，那么 m[i,w]=m[i-1,w-wi]+vi　也就是 i 的前一个的最大值加上自己的价值。
如果不要第 i 个物品，那么：m[i,w]=m[i-1,w]。也就是 i 的前一个的最大值。
因为背包问题最后要取得最大的价值，所以就选这两种情况中价值最大的。
在这个问题中，定义子问题：&m[i,w] 对于每个子问题，都可通过上面的分析求出。通过3），4）可以发现，每一次求取子问题，问题的规模就被缩小。
要么在w 上减小，要么在 i 上减小。最后问题的规模会被缩小为 m[i,0]和m[0,w].而这两个的值都为0，只要逆向思维反推回去，就能逐步得到问题的解。
附c++代码：
&c-free 5编译通过
/*0、1背包问题一条鱼@博客园 /yanlingyin/
*/#include &iostream&#include&fstream&#include&algorithm&#include&vector&//存储元素的结构 typedef struct item{
int}using namespaceint main(){
int weight=10;
int itemnum=4;
//int k[10][4];
vector&vector&int& & k(11,vector&int&(5));
item items[4]={{6,30},{3,14},{4,16},{2,9}};
for(int w=0;w&=w++)
for(int j=0;j&=j++)
k[w][j]=0;
//输出数组
for(int i=0;i&=i++)
for(int j=0;j&=j++)
cout&&k[i][j];
cout&&"\n";
for(int w=1;w&=w++)
cout&&"测试\n";
for(int j=1;j&=j++)
if(items[j-1].weight&w)
//物品质量大于背包容量，舍去
k[w][j]=k[w][j-1];
//对于两种情况选出较大值
k[w][j]=max(k[w][j-1],(k[w-items[j-1].weight][j-1]+items[j-1].values));
cout&&"k["&&w&&"]["&&j&&"]="&&k[w][j]&&"\n";
cout&&"输出哦了"&&k[weight][itemnum]&&"\n";
for(int i=0;i&=i++)
for(int j=0;j&=j++)
cout&&k[i][j]&&" ";
cout&&"\n";
动态规划简单介绍：
动态规划通常用于最优化问题，此类问题可能有很多可行解，每一个解有一个值，而我们希望找出一个具有最优值的解，
动态规划算法设计可分为如下步骤：
1）描述最优解的结构
2）递归定义最优解的值
3）按底向上的方式计算最优解的值
4）由计算出的结果构造一个最优解
动态规划的第一步是描述最优解的结构，如果问题的一个最优解中包含了子问题的最优解，该问题具有最优解结构。当一个子问题
有最优解结构时，提示我们动态规划适用。如本例中的m[i,w]就是一个子问题，里面包含了另一个子问题的最优解：
m[i-1,w],m[i-1,w-1]。解题的过程中把结果记录在数组中，后面的解更具前面的解得出，最后找到问题的解。
参考资料：&
《算法导论》
欢迎转载，请注明出处：
一条鱼@博客园
阅读(...) 评论()菜鸟都能理解的0-1背包问题的空间优化
如果你不知道什么叫做0-1背包问题，下面是0-1背包问题的简单描述
假设有n件物品
每件物品的体积为w1, w2&&wn
& &相对应的价值为 v1, v2.&&vn。
01背包是在n件物品取出若干件放在空间为total_weight的背包里，使得背包的总体积最大
关于0-1背包问题没有优化版本，请看这里
上面的核心代码是下面这一段
for (int i = 1; i &= i++) { &
& for (int j = 1; j &= total_ j++) { &
& & if (w[i] & j) { &
& & & c[i][j] = c[i-1][j]; &
& & } else { &
& & & & if (c[i-1][j] & v[i]+c[i-1][j-w[i]]) { &
& & & & & c[i][j] = c[i-1][j]; &
& & & & } &
& & & & else { &
& & & & & c[i][j] = &v[i] + c[i-1][j-w[i]]; &
& & & & } &
注意到状态转移方程 c[i][j] = max{c[i-1][j], c[i-1][j-w[i]]+v[i]}
每一次c[i][j]改变的值只与c[i-1][x] {x:1...j}有关c[i-1][x]是前一次i循环保存下来的值，因此，可以将c缩减成一维数组
状态转移方程转换为 c[j] = max(c[j], c[j-w[i]]+v[i]);
并且，我们注意到状态转移方程，每一次推导c[i][j]是通过c[i-1][j-w[i]]来推导的，而不是通过c[i][j-w[i]]
因此，j的扫描顺序应该改成从大到小
否则，第i次求c数组，必然先求的c[j-w[i]]的值(即c[i][j-w[i]])，再求c[j](即c[i][j])的值
由于j递增,那么状态方程就成为下面这个样子了
c[i][j] = max(c[i-1][j], c[i][j-w[i]]+v[i])显然不符合题意
所以，上面的代码变为
for (int i = 1; i &= i++) { &
& &for (int j = total_ j &= 1; j--) { &
& & &if (w[i] & j) { &
& & & &c[j] = c[j]; //表示第i次与第i-1次相等，这里因为c[j]本来就保存这上一次的值，所以这里不需变化 &
& & &} else { &
& & & &//说明第i件物品的重量小于背包的重量，所以可以选择第i件物品放还是不放 &
& & & & &if (c[j] & v[i]+c[j-w[i]]) { &
& & & & & &c[j] = c[j]; &
& & & & &} &
& & & & &else { &
& & & & & &c[j] = &v[i] + c[j-w[i]]; &
& & & & &} &
最后我们可以做下优化，把不必要的语句去掉即可完成优化
for (int i = 1; i &= i++) { &
& for (int j = total_ j &= w[i]; j--) { &
& & if (c[j] &= v[i] + c[j-w[i]]) &
& & & c[j] = v[i] + c[j-w[i]]; &
如此优美的代码简直无法想象!
注意，空间优化版本最后是求解不出来最优解序列的，但是能求出最优解，也就是最大价值
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'C++ 算法之回溯求解0-1背包问题 - 开源中国社区
当前访客身份：游客 [
当前位置：
以下是代码部分，关于回溯法求解0-1背包问题，是按照教材上写的，我对照着别人运行通过的代码改过，还是不行，本人菜鸟，对于这种运行能够通过，但是却不显示任何结果的代码无能为力，求大神解释一下这个问题出在哪里，顺便指导下遇到这种错误该怎么破啊？！！本人不甚感激啊&&大神指点啊~~~~
#include &iostream&
//剪枝函数
int Bound(int M,int n,int w[],int p[],int pn,int wn,int k)
for(int i=k+1;i&=n;i++)
return (b+p[i]/w[i]*(M-c+w[i]));
//先假设各个物品重量都是整数
物品的个数
背包承受的最大重量
最大效益值
当前情况下背包中的总效益值
当前背包中的总重量
int BKnap1(int M,int n,int w[],int p[])
int wEnd=0;
int pMax=-1;
int x[9]={-1,-1,-1,-1,-1,-1,-1,-1,-1};
while(true)
while(k&n&&wn+w[k]&=M)
wn=wn+w[k];
pn=pn+p[k];
cout&&&最大效益值为：
cout&&&此时背包重量：
cout&&&解向量：&&&
for(int i=0;i&=n;i++)
cout&&x[i]&&&
else x[k]=0;
//回溯部分的实现
while(Bound(M,n,w,p,pn,wn,k)&=pMax)
while(k!=-1&&x[k]!=1)
wn=wn-w[k];
pn=pn-p[k];
int main()
int M=110;
int p[8]={11,21,31,33,43,53,55,65};
int w[8]={1,11,21,23,33,43,45,55};
int a=BKnap1(M,n,w,p);
共有0个答案
更多开发者职位上
有什么技术问题吗？
瑞瑞610的其它问题
类似的话题8075人阅读
ACM-动态规划（40）
今天看了看背包九讲，自己写了下0-1背包和完全背包
王晓东《计算机算法分析与设计》上面给出的C++实现比较繁琐，相比而言这个版本更加简明
给出了测试数据
0-1背包问题C++实现
/*任务：计算0-1背包问题的最大价值
Sample Input
Sample Output
#include&stdio.h&
#include&string.h&
int c[20][1000];//c[k][y]为只允许装前k种物品，背包总重量不超过y的最大价值
int inumber[21][1000];//inumber[k][u]为只允许装前K种物品，背包总重量不超过y时得到最大价值时使用的背包的最大标号
int w[21],p[21];
int knapsack(int m,int n)
for(i=1;i&n+1;i++)
scanf(&%d%d&,&w[i],&p[i]);
memset(c,0,sizeof(c));
memset(inumber,0,sizeof(inumber));
for(j=1;j&m+1;j++){
c[1][j]=j/w[1]*p[1];
for(i=1;i&n+1;i++){
for(j=1;j&m+1;j++){
if(j &= w[i]){
if(p[i]+c[i-1][j-w[i]]&=c[i-1][j]){
c[i][j]=p[i]+c[i-1][j-w[i]];
inumber[i][j]=i;
c[i][j]=c[i-1][j];
inumber[i][j]=inumber[i-1][j];
c[i][j]=c[i-1][j];
inumber[i][j]=inumber[i-1][j];
return(c[n][m]);
void trackSolution(int m, int n){
int x[21];
memset(x, 0, sizeof(x));
while(true){
j = inumber[j][y];
y = y - w[j];
while(inumber[j][y] == j){
y = y - w[j];
if(!inumber[j][y])
printf(&最大价值方案中各个物品的个数为(物品标号从1到n)：&);
for(j = 1; j &= j++){
printf(&%d &, x[j]);
printf(&\n&);
int main()
while(scanf(&%d%d&,&m,&n)!=EOF){
printf(&最大价值为%d\n&,knapsack(m,n));
trackSolution(m, n);
完全背包问题C++实现
/*任务：计算完全背包问题的最大价值
Sample Input
Sample Output
#include&stdio.h&
#include&string.h&
int c[20][1000];//c[k][y]为只允许装前k种物品，背包总重量不超过y的最大价值
int inumber[21][1000];//inumber[k][u]为只允许装前K种物品，h背包总重量不超过y时得到最大价值时使用的背包的最大标号
int w[21],p[21];
int knapsack(int m,int n)
for(i=1;i&n+1;i++)
scanf(&%d%d&,&w[i],&p[i]);
memset(c,0,sizeof(c));
memset(inumber,0,sizeof(inumber));
for(j=1;j&m+1;j++){
c[1][j]=j/w[1]*p[1];
for(i=1;i&n+1;i++){
for(j=1;j&m+1;j++){
if(j &= w[i]){
if(p[i]+c[i][j-w[i]]&=c[i-1][j]){//和0-1背包相比只是将c[i-1][j-w[i]]写成了c[i][j-w[i]]，因为完全背包问题中每件物品有无限个
c[i][j]=p[i]+c[i][j-w[i]];
inumber[i][j]=i;
c[i][j]=c[i-1][j];
inumber[i][j]=inumber[i-1][j];
c[i][j]=c[i-1][j];
inumber[i][j]=inumber[i-1][j];
return(c[n][m]);
void trackSolution(int m, int n){
int x[21];
memset(x, 0, sizeof(x));
while(true){
j = inumber[j][y];
y = y - w[j];
while(inumber[j][y] == j){
y = y - w[j];
if(!inumber[j][y])
printf(&最大价值方案中各个物品的个数为(物品标号从1到n)：&);
for(j = 1; j &= j++){
printf(&%d &, x[j]);
printf(&\n&);
int main()
while(scanf(&%d%d&,&m,&n)!=EOF){
printf(&最大价值为%d\n&,knapsack(m,n));
trackSolution(m, n);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1000765次
积分：11318
积分：11318
排名：第907名
原创：236篇
转载：36篇
评论：713条
(3)(4)(1)(9)(5)(6)(4)(19)(13)(25)(2)(13)(7)(2)(1)(1)(1)(1)(1)(4)(1)(6)(3)(2)(2)(4)(9)(11)(5)(24)(17)(1)(27)(36)(1)(2)(2)