背包问题-C语言代码

背包问题的三种解法实验报告实验要求：分别用动态规划法、回溯法、分支限界法解决0/1 背包问题，了解三种算法的算法步骤并上机实现。

实验步骤：1. 建立一个背包问题的解法类Bag.h。

bag_m为动态规划法，bag_b为回溯法，bag_t为分支限界法。

2. 建立一个排序类Sort1.h。

程序的需要对背包的价值比排序。

3. 由分支限界建立一个动态的最大堆及堆的各种操作和运算类SqList.h。

代码实现：1. 主函数：// 背包问题的解法#include <iostream> #include "Bag.h"// 背包问题处理方法类using namespace std;int main() int i,n,M;coutvv"请输入物品个数：";cin>>n;double *m=new double[n+1];double *p=new double[n+1];coutvv"输入每个物品的重量：";for(i=1;i<=n;i++)cin>>m[i];coutvv"输入每个物品的价值:for(i=1;i<=n;i++)cin>>p[i];coutvv"请输入背包的重量：";cin>>M;Bag bag;//创建一个背包问题的解法类对象coutvv"选择背包问题的解法，输入1,动态规划法，输入2,回溯法，输入3,分支限界法。

"vv'\n'vv"请输入1或者2,或者输入3："<<"";cin>>i;if(i==1)bag.bag_m(m, p,n,M);//调用动态规划法if(i==2)bag.bag_b(m, p,n,M);// 调用回溯法if(i==3)bag.bag_t(m, p,n ,M);//调用分支限界法return 0;2. 排序方法类：（Filename：Sort1.h）// 合并排序类（合并排序）#include <iostream>using namespace std;struct objdouble m;double p;double v;};typedef struct obj OBJ; // 定义物体的数据结构class Sort1public:void merge_sort(OBJ a[],int n)// 以物体的价值比排序int i,s,t=1;while(t<n)s=t;t=2*s;i=0;while(i+t<n)merge(a,i,i+s-1,i+t-1,t);i=i+t;if(i+s<n)merge(a,i,i+s-1,n-1,n-i);void merge(OBJ a[],int p,int q,int r,int n)OBJ *bp=new OBJ[n];int i,j,k;i=p;j=q+1;k=0;while(i<=q&&j<=r)if(a[i].v<=a[j].v)bp[k++]=a[i++];elsebp[k++]=a[j++];if(i==q+1)for(;j<=r;j++)bp[k++]=a[j];elsefor(;i<=q;i++)bp[k++]=a[i];k=0;for(i=p;i<=r;i++)a[i]=bp[k++];delete bp;};3. 背包问题解法类：（Filename：Bag.h）// 背包问题方法类（包含三种方法）//bag_m 动态规划法//bag_b 回溯法//bag_t 分支限界法#include <iostream>using namespace std;#include "Sort1.h"#include "SqList.h"class Bagpublic:void bag_m(double *m,double *p,int n,int M)// 动态规划法int i,j;int *x=new int[n+1];OBJ *objs=new OBJ[n+1];objs[0].p=0;objs[0].v=0;for(i=1;i<=n;i++)objs[i].m=m[i];objs[i].p=p[i];objs[i].v=objs[i].m/objs[i].p;double **optp;optp=new double *[n+1]; for(i=0;i<n+1;i++)optp[i]=new double[M+1]; x[i]=0;for(i=0;i<=n;i++)optp[i][0]=0;for(i=0;i<=M;i++)optp[0][i]=0;for(i=1;i<=n;i++)for(j=1;j<=M;j++)optp[i][j]=optp[i-1][j];elseoptp[i][j]=optp[i-1][j];if(optp[i][j]<(optp[i-1][int(j-objs[i].m)]+objs[i].p)) optp[i][j]=(optp[i-1][int(j-objs[i].m)]+objs[i].p);i=n;j=M;while(i&&j)if(optp[i][j]>optp[i-1][j])x[i]=1;j-=objs[i].m;elsex[i]=0;cout<<" 输出结果，装入为1，不装入为0:"<<'\n'; for(i=1;i<=n;i++)cout<<x[i]<<" ";}cout<<'\n';coutvv"背包物体的总价值最大为："VVO ptp[n ][M]VV'\n：delete x,objs;for(i=0;i<=n;i++)delete [] optp[i];delete optp;void bag_b(double *m,double *p,int n,int M)// 回溯法int i,j,k;int *x=new int[n+1];int *y=new int[n+2];double m_cur,m_est,p_cur,p_est,p_total;m_cur=0;p_cur=0;p_total=0;OBJ *objs=new OBJ[n+1];objs[0].m=0;objs[0].p=0;objs[0].v=0;for(i=1;i<=n;i++)objs[i].m=m[i];objs[i].p=p[i];objs[i].v=objs[i].m/objs[i].p;y[i]=0;x[i]=0;y[n+1]=0;Sort1 sort;sort.merge_sort(objs,n+1);// 排序k=1;while(k>=1)p_est=p_cur;m_est=m_cur;for(i=k;i<=n;i++)m_est=m_est+objs[i].m;if(m_est<M)p_est=p_est+objs[i].p;elsep_est=p_est+((M-m_est+objs[i].m)/objs[i].m)*objs[i].p;break; if(p_est>p_total)for(i=k;i<=n;i++)if(m_cur+objs[i].m<=M) m_cur+=objs[i].m;p_cur+=objs[i].p;y[i]=1;else {y[i]=0; break;}if(i>=n)if(p_cur>p_total)p_total=p_cur;k=n+1; for(j=1;j<=n;j++)x[j]=y[j];else k=i+1;elsewhile(i>=1&&y[i]==0)if(i<1) break;elsem_cur-=objs[i].m;p_cur-=objs[i].p;y[i]=0;k=i+1;for(i=1;i<=n;i++)cout<<x[i];cout<<'\n';cout<<"total="<<p_total;delete x,y,objs;void bag_t(double *m,double *p,int n,int M)// 分支限界法int i;double t;OBJ *ob=new OBJ[n];for(i=0;i<n;i++)ob[i].m=m[i+1];ob[i].p=p[i+1];ob[i].v=ob[i].m/ob[i].p;Sort1 sort;sort.merge_sort(ob,n);Knapnode kn a,k nax,k nay;//定义左节点和右节点kna.b=0;kna.k=0;kna.p=0;kna.w=0;for(i=0;i<5;i++)kna.s1[i]=0;for(i=kna.k,t=kna.w;i<n;i++)if(t+ob[i].m<=M)t+=ob[i].m;kna.b+=ob[i].p;elsekna.b+=(M-t)*ob[i].p/ob[i].m;break;sqlist q;SqList sq;sq.InitList_Sq(q);sq.insert(q,kna);while(q.length!=0)kna=sq.delete_max(q);if(kna.k==5)}}cout<<"the value is:"<<kna.p<<'\n'; for(i=0;i<5;i++)cout<<kna.s1[i]<<" ";cout<<'\n';break;knay=kna;knay.k++;knay.b=knay.p;for(i=knay.k,t=knay.w;i<n;i++)if(t+ob[i].m<=M)t+=ob[i].m;knay.b+=ob[i].p;elseknay.b+=(M-t)*ob[i].p/ob[i].m;break;sq.insert(q,knay);knax=kna;if(knax.w+ob[knax.k].m>M)continue;knax.s1[knax.k]=1;knax.w+=ob[knax.k].m;knax.p+=ob[knax.k].p;knax.k++;sq.insert(q,knax);};4.动态堆方法类（分支限界方法中用到，Filename：SqList.h）// 动态最大堆#include <iostream>#include "math.h"#include <iomanip>using namespace std;#define ListInitSize 20#define ListIncrement 10const n=5;typedef structint s1[n];int k;float b;float w;float p;}Knapnode;typedef struct sqListKnapnode *elem;int length;int listsize;}sqlist;class SqList/动态堆类public:void InitList_Sq(sqlist &L)//n 为单位元素的大小，初始化堆L.elem=(Knapnode *)malloc(ListInitSize* sizeof(Knapnode));if(L.elem==NULL) exit(OVERFLOW);L.length=0;L.listsize=ListInitSize;void ListI nsert_Sq(sqlist & L,K napn ode elem)/向堆中插入节点Knapnode * newbase;if(L.length>=L.listsize)newbase=(Knapnode*)realloc(L.elem,(L.listsize+ListIncrement)sizeof(Knapnod e))if(newbase==NULL) exit(OVERFLOW);L.elem=newbase;L.listsize+=ListIncrement;L.elem[++L.length]=elem;void sift_up(sqlist &L,int i)// 上移操作while(i>=2)*if(L.elem[i].b>L.elem[i/2].b)swap(L.elem[i/2],L.elem[i]);i/=2;else break;void sift_down(sqlist &L,int i)// 下移操作int done=0;i=2*i;while(done==0&&i<=L.length)if(i+1<=L.length&&L.elem[i+1].b>L.elem[i].b) i++;if(L.elem[i/2].b<L.elem[i].b)swap(L.elem[i/2],L.elem[i]);else done=1;void swap(Knapnode &a,Knapnode &b)Knapnode t;t=a;a=b;b=t;void in sert(sqlist & L,Kna pn ode x)//插入节点后，并排序ListInsert_Sq(L,x);sift_up(L,L.length);Kna pn ode delete_max(sqlist & L)//删除堆中预测价值的最大者Knapnode p;p=L.elem[1];swap(L.elem[1],L.elem[L.length]);L.length--;sift_down(L,1);return p;void print(sqlist &L)// 打印堆的数据int i;};for(i=1;i<=L.length;i++)cout<<L.elem[i].b;运行方法和结果（用这三种算法分别给出实验结果）：1. 动态规划法：2. 回溯法：3. 分支限界法。

C-SHARP 编程求解背包问题源代码//前面用EXCEL解决的背包问题，下面用C#语言来模仿EXCEL的解决思路求解背包问题//本程序没有对用户输入的合法性进行的检测，有待改进。

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace backbag{class Program{static void Main(string[] args){Console.WriteLine("");Console.WriteLine("-------------------欢迎使用背包问题计算器-------------------");Console.WriteLine(" ");Console.WriteLine("****************************************** ******************");Console.WriteLine("** 本程序的用途：在一组数据中，有不定个数的数据之和为 **");Console.WriteLine("** 一个特定的值，本程序可以求出该数据组所有的排列组合方式 **");Console.WriteLine("** 注意：本程序由于算法和数据类型限制，最多只能处理32 **");Console.WriteLine("** 个数据。

**");Console.WriteLine("****************************************** ******************");Console.WriteLine(" ");Console.WriteLine("》编程语言：C-SHARP 》程序类型：控制台程序》作者：陈东昇");Console.WriteLine("》开发工具：VS2008 》开发时间：2016-01-01 》版本号：V1.0");Console.WriteLine("------------------------------------------------------------");Console.WriteLine(" ");/* 以上代码，显示程序基本信息*/int totalLength=0;Console.Write("请输入数据个数（1~32之间）：");for (int i = 0;i<1 ; ){totalLength =Convert.ToInt32(Console.ReadLine()); //用户输入一个数字，将totalLength用来存储数组的长度；if (totalLength > 32 ){i=0;Console.Write("数字太大，请重新输入（1~32之间）:");}else if (totalLength < 1){i = 0;Console.Write("数字太小，请重新输入（1~32之间）:");}else if (totalLength <= 32 || totalLength >= 1){i = 1;}}Console.WriteLine();double[] theData = newdouble[totalLength]; //theData用来存储要处理的数据；double[] resule = newdouble[totalLength]; //用来保存最终的数组结果uint maxTime =0; //用maxTime来保存所有排列组合的个数；stringrunTime; //用 runTime 来保存maxTime的二进制字符串。

动态规划------背包问题（c语⾔）/*背包问题:背包所能容纳重量为10；共五件商品，商品重量⽤数组m存储m[5]={2,2,6,5,4},每件商品的价值⽤数组n存储,n[5]={6,3,5,4,6};求背包所能装物品的最⼤价值。

*/#include<stdio.h>#include<conio.h>int main() {int m[5] = { 2,2,6,5,4 }, n[5] = { 6,3,5,4,6 };int flag[5] = { 0,0,0,0,0 };//符号标志位，表⽰地某个点是否装⼊背包，装⼊为1，未装⼊为0；int i, j, k;int c = 10, sum1 = 0, sum2 = 0;//sum1表⽰最终背包容纳的重量。

sum2表⽰最终背包中容纳的最⼤价值的价值。

//设⼀个⼆维数组，横坐标表⽰所装物品的标号，纵坐标表⽰背包所容纳的最⼤重量0~10；int mn[5][11];for (i = 4; i >= 0; i--) {//⼆维数组从下⾄上for (j = 0; j <= 10; j++) {if (i == 4) {if (m[i]>j)mn[i][j] = 0;elsemn[i][j] = n[i];}else {if (m[i]>j) {mn[i][j] = mn[i + 1][j];}else {mn[i][j] = mn[i + 1][j]>mn[i + 1][j - m[i]] + n[i] ? mn[i + 1][j] : mn[i + 1][j - m[i]] + n[i];}}}}for (i = 0; i<5; i++) {if (mn[i][c] != mn[i + 1][c]) {//从⼆维数组上⽅开始，背包最⼤值c,mn[i][c]的值若与mn[i+1][c]的值不同，则m[i]未放⼊背包中（之前是⾃下往上放的） flag[i] = 1;c = c - m[i];//若放⼊背包，则背包可容纳总重量减少；}printf("%d ", flag[i]);}//输出所放⼊的物品序号for (i = 0; i<5; i++) {if (flag[i] == 1) {sum1 += m[i];sum2 += n[i];}}printf("\n背包容纳的重量为：%d 背包容纳的总价值为：%d", sum1, sum2);getch();return0;}。

以下是使用C语言实现01背包问题的回溯法代码：```c#include <stdio.h>#include <stdlib.h>// 初始化背包struct knapsack {int maxWeight; // 背包最大承重int *items; // 物品数组int n; // 物品数量};// 定义物品重量、价值和数量int weights[] = {2, 2, 6, 5, 4};int values[] = {6, 3, 5, 4, 6};int quantities[] = {3, 2, 2, 1, 1};// 初始化背包最大承重和当前承重int maxWeight = 10;int currentWeight = 0;// 初始化最大价值为0int maxValue = 0;// 遍历物品数组void traverseItems(struct knapsack *knapsack, int index) { // 对于每个物品，遍历其数量for (int i = 0; i < knapsack->quantities[index]; i++) {// 如果当前物品可以放入背包装且当前承重不超过背包最大承重，计算放入该物品后的总价值，并更新最大价值if (currentWeight + weights[index] <= knapsack->maxWeight) {int currentValue = values[index] * knapsack->quantities[index];if (currentValue > maxValue) {maxValue = currentValue;}}// 回溯，将当前物品从背包装中移除，递归地尝试下一个物品knapsack->quantities[index]--;if (index < knapsack->n - 1) {traverseItems(knapsack, index + 1);}knapsack->quantities[index]++; // 恢复物品数量，以便下次遍历尝试放入其他物品}}// 主函数int main() {// 初始化背包装和物品数组struct knapsack knapsack = {maxWeight, weights, 5};knapsack.items = (int *)malloc(sizeof(int) * knapsack.n);for (int i = 0; i < knapsack.n; i++) {knapsack.items[i] = values[i] * quantities[i]; // 根据价值和数量计算物品价值，并存储在物品数组中}knapsack.n = quantities[4]; // 由于最后一个物品的数量为1，因此只需遍历前n-1个物品即可得到所有可能的结果// 使用回溯法求解01背包问题，返回最大价值traverseItems(&knapsack, 0);printf("The maximum value is %d.\n", maxValue);free(knapsack.items); // 释放内存空间return 0;}```希望以上信息能帮助到你。

背包问题实验题目：背包问题问题描述：假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, … , wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+ wn=T，要求找出所有满足上述条件的解。

例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）。

概要设计：采用栈数据结构，利用回溯法的设计思想来解决背包问题。

首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。

但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。

ADT Stack {数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n,n≥0 }数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }约定an端为栈顶，a1端为栈底。

基本操作：InitStack(&S)操作结果：构造一个空栈S。

DestroyStack(&S)初始条件：栈S已存在。

操作结果：栈S被销毁。

ClearStack(&S)初始条件：栈S已存在。

操作结果：将S清为空栈。

StackEmpty(S)初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则FALSE。

StackLength(S)初始条件：栈S已存在。

操作结果：返回S的元素个数，即栈的长度。

GetTop(S, &e)初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。

Push(&S, e)初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

13.背包问题（Knapsack Problem）说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价解法背包问题是关于最佳化的问题，要解最佳化问题可以使用「动态规划」（Dynamicprogramming），从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。

以背包问题为例，我们使用两个阵列value与item，value表示目前的最佳解所得之总价，item 表示最后一个放至背包的水果，假设有负重量1～8的背包8个，并对每个背包求其最佳解。

逐步将水果放入背包中，并求该阶段的最佳解：放入李子放入苹果放入橘子放入草莓放入甜瓜由最后一个表格，可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入的水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤（8-1）的水果，所以必须看背包负重7公斤时的最佳解，最后一个放入的是2号，也就是橘子，现在背包剩下负重量5公斤（7-2），所以看负重5公斤的最佳解，最后放入的是1号，也就是苹果，此时背包负重量剩下0公斤（5-5），无法再放入水果，所以求出最佳解为放入草莓、橘子与苹果，而总价为9050元。

实作C#include <stdio.h>#include <stdlib.h>#define LIMIT 8 // 重量限制#define N 5 // 物品种类#define MIN 1 // 最小重量struct body {char name[20];int size;int price;};typedefstruct body object;int main(void) {int item[LIMIT+1] = {0};int value[LIMIT+1] = {0};intnewvalue, i, s, p;object a[] = {{"李子", 4, 4500},{"苹果", 5, 5700},{"橘子", 2, 2250},{"草莓", 1, 1100},{"甜瓜", 6, 6700}};for(i = 0; i< N; i++) {for(s = a[i].size; s <= LIMIT; s++) {p = s - a[i].size;newvalue = value[p] + a[i].price;if(newvalue> value[s]) {// 找到阶段最佳解value[s] = newvalue;item[s] = i;}}}printf("物品\t价格\n");for(i = LIMIT; i>= MIN; i = i - a[item[i]].size) {printf("%s\t%d\n",a[item[i]].name, a[item[i]].price);}printf("合计\t%d\n", value[LIMIT]);return 0;}附砝码称重#include<stdio.h>int main(){intn,i;intvec[]={1,3,9,27,81};while(scanf("%d",&n)!=EOF){int first=0;n+=121;for(i=4;i>=0;n%=vec[i--])switch(n/vec[i]){case 0:printf("-%d",vec[i]);++first;break;case 2:printf("%s%d",first?"+":"",vec[i]);++first;}printf("\n");}}。

C语⾔动态规划之背包问题详解01背包问题给定n种物品，和⼀个容量为C的背包，物品i的重量是w[i],其价值为v[i]。

问如何选择装⼊背包的物品，使得装⼊背包中的总价值最⼤？（⾯对每个武平，只能有选择拿取或者不拿两种选择，不能选择装⼊某物品的⼀部分，也不能装⼊物品多次）声明⼀个数组f[n][c]的⼆维数组，f[i][j]表⽰在⾯对第i件物品，且背包容量为j时所能获得的最⼤价值。

根据题⽬要求进⾏打表查找相关的边界和规律根据打表列写相关的状态转移⽅程⽤程序实现状态转移⽅程真题演练：⼀个旅⾏者有⼀个最多能装M公⽄的背包，现在有n件物品，它们的重量分别是W1、W2、W3、W4、…、Wn。

它们的价值分别是C1、C3、C2、…、Cn,求旅⾏者能获得最⼤价值。

输⼊描述：第⼀⾏：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30);第2…N+1⾏：每⾏两个整数Wi，Ci，表⽰每个物品的质量与价值。

输出描述：仅⼀⾏，⼀个数，表⽰最⼤总价值样例：输⼊：10 42 13 34 57 9输出：12解题步骤定义⼀个数组dp[i][j]表⽰容量为j时，拿第i个物品时所能获取的最⼤价值。

按照题⽬要求进⾏打表，列出对应的dp表。

W[i]（质量）V[i]（价值）01234567891000000000000210011111111133001334444444500135568899790013556991012对于⼀个动态规划问题设置下标时最好从0开始，因为动态规划经常会和上⼀个状态有关系！从上⾯的dp表可以看出来对于⼀个物品我们拿还是不难需要进⾏两步来判断。

第⼀步：判断背包当前的容量j是否⼤于物品当前的质量，如果物品的质量⼤于背包的容量那么就舍弃。

第⼆步：如果背包可以装下这个物品，就需要判断装下该物品获取的最⼤价值是不是⼤于不装下这个物品所获取的最⼤价值，如果⼤于那么就把东西装下！根据这样的思想我们可以得到状态转移⽅程：如果单签背包的容量可以装下物品:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);如果当前背包的容量装不下该物品:dp[i][j]=dp[i-1][j];#include <stdio.h>int max(const int a,const int b){return a>b ? a:b;}int main(){int w[35]={0},v[35]={0},dp[35][210]={0};int n,m;scanf("%d %d",&m,&n);int i,j;for(i=1;i<=n;i++){scanf("%d %d",&w[i],&v[i]);}for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(j>=w[i])//如果当前背包的容量⼤于商品的质量{dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//判断是否应该拿下}else//⼤于背包的当前容量{dp[i][j]=dp[i-1][j];}}}for(int k=0;k<=n;k++){for(int l=0;l<=m;l++){printf("%d ",dp[k][l]);}printf("\n");}printf("%d\n",dp[n][m]);}通过运⾏以上程序可以看到最终的输出dp表和我们的预期是相符合的！但是并没有结束，动态规划有⼀个后⽆效性原则(当前状态只与前⼀个状态有关)。

0/1 背包问题动态规划详解及C代码动态规划是用空间换时间的一种方法的抽象。

其关键是发现子问题和记录其结果。

然后利用这些结果减轻运算量。

比如01背包问题。

/* 一个旅行者有一个最多能用M公斤的背包，现在有N件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为P1,P2,...,Pn.若每种物品只有一件求旅行者能获得最大总价值。

输入格式：M,NW1,P1W2,P2......输出格式：X*/因为背包最大容量M未知。

所以，我们的程序要从1到M一个一个的试。

比如，开始任选N 件物品的一个。

看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。

怎么能保证总选择是最大价值呢？看下表。

测试数据：10,33,44,55,6c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。

加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。

总的最佳方案是5+4为9.这样.一排一排推下去。

最右下放的数据就是最大的价值了。

(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)从以上最大价值的构造过程中可以看出。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?下面是实际程序（在VC 6.0环境下通过）:#include<stdio.h>int c[10][100];/*对应每种情况的最大价值*/int knapsack(int m,int n){int i,j,w[10],p[10];printf("请输入每个物品的重量,价值：\n");for(i=1;i<=n;i++)scanf("%d,%d",&w[i],&p[i]);for(i=0;i<10;i++)for(j=0;j<100;j++)c[i][j]=0;/*初始化数组*/for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(w[i]<=j) /*如果当前物品的容量小于背包容量*/{if(p[i]+c[i-1][j-w[i]]>c[i-1][j])/*如果本物品的价值加上背包剩下的空间能放的物品的价值*//*大于上一次选择的最佳方案则更新c[i][j]*/c[i][j]=p[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}else c[i][j]=c[i-1][j];}return(c[n][m]);}int main(){int m,n;int i,j;printf("请输入背包的承重量,物品的总个数：\n");scanf("%d,%d",&m,&n);printf("旅行者背包能装的最大总价值为%d",knapsack(m,n)); printf("\n");return 0;}。

0-1背包问题c语言实现问题描述:给定n种物品和一个背包。

物品i的重量为w[i]，其价值为v[i]，背包的容量为c。

应如何选择装入背包的物品，使得装入背包中的物品的总价值最大。

每种物品最多装入一次。

0-1背包问题：对于要装入背包中的物品，只有两种选择：全部装入或者不装入。

背包问题：对于要装入背包中的物品，可以选择装入一部分，不一定要全部装入背包中。

算法分析：使用贪心策略求解此类问题时，首先要选出最优的度量标准。

可供选择的度量标准有三种：价值，容量，单位价值（v/w，价值/重量）。

显然，价值高的物品容量可能太大，容量大的物品价值也可能很低。

最优的度量标准是单位价值。

背包问题算法思路：1、将各个物品按照单位价值由高到低排序；2、取价值最高者放入背包；3、计算背包的剩余空间；4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。

下面是C语言实现（DEV c++4.9.9.2运行通过）[cpp]#includevoid package(int n,float c,float v[],float w[],float x[]); void package0_1(int n,float c,float v[],float w[],float x[]);int main(void){int n = 3;float c = 20;float v[] = {24,15,25};float w[] = {15,10,18};//已经按照单位价值降序排列float *x;x = (float*)malloc(sizeof(float)*n);printf("******背包*******\n");package(n,c,v,w,x);printf("*******0-1背包******\n");package0_1(n,c,v,w,x);system("PAUSE");}/** 背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）*/void package(int n,float c,float v[],float w[],float x[]){int i;for(i=0;i{x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i{if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);}if(i<=n)//还可以放入一个物品的一部分{x[i] = c/w[i];printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);}}/** 0-1背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入）*/void package0_1(int n,float c,float v[],float w[],float x[]) {int i;for(i=0;i{x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i{if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c); }}#includevoid package(int n,float c,float v[],float w[],float x[]); void package0_1(int n,float c,float v[],float w[],float x[]);int main(void){int n = 3;float c = 20;float v[] = {24,15,25};float w[] = {15,10,18};//已经按照单位价值降序排列float *x;x = (float*)malloc(sizeof(float)*n);printf("******背包*******\n");package(n,c,v,w,x);printf("*******0-1背包******\n");package0_1(n,c,v,w,x);system("PAUSE");}/** 背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）*/void package(int n,float c,float v[],float w[],float x[]){int i;for(i=0;i<n;i++){x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i<n;i++){if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);}if(i<=n)//还可以放入一个物品的一部分{x[i] = c/w[i];printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);}}/** 0-1背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入）*/void package0_1(int n,float c,float v[],float w[],float x[]){int i;for(i=0;i<n;i++){x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i<n;i++){if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);}}虽然背包问题和0-1背包都具有最优子结构性质，但是背包问题用贪心算法求出来的是最优解，0-1背包问题通过贪心算法得不到最优解，因为无法保证最后能将背包装满，部分闲置的背包空间使总价值降低了。

背包问题：clearclcpopsize=500;%种群大小n=50;CW=1000;%背包大小可容纳的总重量w=[80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 ...40 38 35 32 25 28 30 22 50 30 45 30 60 50 20 65 20 25 30 10 ...20 25 15 10 10 10 4 4 2 1];%各个物品的重量，50个个体v=[220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 ...100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 60 58 ...56 50 30 20 15 10 8 5 3 1];%各个物品的价值，50个个体t=100;%迭代次数pc=0.9;%交叉率pm=0.05;%变异率pop=initpop(popsize,n); %产生初始种群for i=1:500[objvalue]=calobjvalue(pop,n,popsize,v,w,CW); %计算目标函数[fitvalue]=calfitvalue(objvalue);%计算群体中每个个体的适应度[newpop]=selection(pop,fitvalue);%进行选择计算[newpop1]=crossover(newpop,pc);%进行交叉计算[newpop2]=mutation(newpop1,pm);%进行变异计算[newobjvalue]=newcalobjvalue(newpop2,n,popsize,v,w,CW); %计算最新代目标函数值，经过选择交叉变异后的下一代[newfitvalue]=newcalfitvalue(newobjvalue);%计算最新代的个体适应度[bestweight,bestvalue]=best(newpop2,newfitvalue,w); %计算最优个体重量，价值，和位置y(i)=max(bestvalue);%记录最大价值g(i)=max(bestweight);%记录最大重量n(i)=i;%记录位置pop=newpop2;%迭代重复endi=1:500;plot(y(i),'-b*')xlabel('迭代次数')ylabel('最大价值');title('最优点变化趋势');legend('最优点');grid on[z index]=max(y);po=n(index)%最优代数位置W=g(index)%最优重量V=z%最优价值%误差率计算%文献中的结果：算法最大迭代次数总价值为总重量为%传统的算法4003077999%佳点集算法7031031000%遗传算法7531031000%本程序中的计算与文献结果的比较p1=(3077-V)/3077%与传统算法相比的误差率p2=(3103-V)/3103%与佳点集算法相比的误差率p3=(3103-V)/3103%与贪心算法遗传算法相比的误差率function [bestweight,bestvalue]=best(newpop2,newfitvalue,w) %寻找最优个体，包括其重量和价值。

关于⼏个背包问题（C语⾔）（1）01背包：01背包的状态转换⽅程 f[i,j] = Max{ f[i-1,j-Wi]+Pi, f[i-1,j] }f[i,j]表⽰在前i件物品中选择若⼲件放在承重为 j 的背包中，可以取得的最⼤价值。

Pi表⽰第i件物品的价值。

该⽅程说⽩了就是⽐较放第i个和不放第i个物品两种决策，哪种决策价值⼤就选择哪种。

我们举个例⼦来理解下：假设f[i-1,j]表⽰我有⼀个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装⼊的最⼤价值9,现在有个重量Wi为2 价值为Pi为6的物品a，考虑是否放⼊承重为8的背包使其价值最⼤，f[i-1,j-Wi]代表⼀个承重为6的背包的最⼤价值（等于当前背包承重8减去物品a的重量2），当只有物品b,c,d,e四件可选时,这个背包能装⼊的最⼤价值为8由于f[i-1][v-Wi]+w[i]= 9 + 6 = 15 ⼤于f[i][v] = 8，所以物品a应该放⼊承重为8的背包。

总的来说：⽅程之中，现在需要放置的是第i件物品，这件物品的重量是Wi,价值是Pi,因此f[i-1,j]代表的就是不将这件物品放⼊背包，⽽f[i-1],j-Wi]]+Pi则是代表将第i件放⼊背包之后的总价值，⽐较两者的价值，得出最⼤的价值存⼊现在的背包之中。

附上南阳oj上的⼀个题(49题)：开⼼的⼩明时间限制：1000 ms | 内存限制：65535 KB难度：4描述⼩明今天很开⼼，家⾥购置的新房就要领钥匙了，新房⾥有⼀间他⾃⼰专⽤的很宽敞的房间。

更让他⾼兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就⾏”。

今天⼀早⼩明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。

于是，他把每件物品规定了⼀个重要度，分为5 等：⽤整数1~5 表⽰，第5 等最重要。

他还从因特⽹上查到了每件物品的价格（都是整数元）。

他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最⼤。

背包问题系列（01背包、完全背包、多重背包）背包问题是⼀个经典的动态规划问题，问题可以描述为：给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。

根据给定物品的数量，背包问题⼜可分为：1）每种物品只有⼀件，即01背包问题2）每种物品不限数量，可选取任意数量，即完全背包问题3）每种物品的数量已给定，不可超出该数量，即多重背包问题背包问题的重点：1）编写状态转移⽅程2）空间优化1 #include <iostream>2 #include <vector>3using namespace std;45int max(int a, int b)6 {7return a > b ? a : b;8 }910int min(int a, int b)11 {12return a < b ? a : b;13 }1415// 01背包问题,n件物品，重量为v16int BagProblem_01(const vector<int> &weight, const vector<int> &value, int n, int v)17 {18// 前i件物品背包限重为j的情况下的最⼤值19 vector<vector<int>> dp(n, vector<int>(v + 1, 0));2021for (int i = 0; i <= v; i++)22 {23if (i >= weight[0])24 {25 dp[0][i] = value[0];26 }27 }2829for (int i = 1; i < n; i++)30 {31for (int j = 1; j <= v; j++)32 {33if (j < weight[i])34 {35 dp[i][j] = dp[i - 1][j];36 }37else38 {39 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);40 }41 }42 }4344return dp[n - 1][v];45 }4647// 01背包问题--优化空间48int BagProblem_01_optimize(const vector<int> &weight, const vector<int> &value, int n, int v)49 {50// 前i件物品背包限重为j的情况下的最⼤值51 vector<int> dp(v + 1, 0);5253for (int i = 0; i <= v; i++)54 {55if (weight[0] > v)56 {57 dp[0] = value[0];58 }59 }6061for (int i = 1; i < n; i++)62 {63for (int j = v; j >= weight[i]; j--) // dp[j]是由上⼀⾏<=j列推出，j需逆向枚举64 {65 dp[j] = max(dp[j], dp [j - weight[i]] + value[i]);66 }67 }6869return dp[v];70 }7172// 完全背包问题73int BagProblem_complete(const vector<int> &weight, const vector<int> &value, int n, int v)74 {75 vector<vector<int>> dp(n, vector<int>(v + 1, 0));7677for (int j = 0; j <= v; j++)78 {79 dp[0][j] = j / weight[0] * value[0];80 }8182for (int i = 1; i < n; i++)83 {84for (int j = 0; j <= v; j++)85 {86if (j < weight[i])87 {88 dp[i][j] = dp[i - 1][j];89 }90else91 {92 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);93 }94 }95 }9697return dp[n - 1][v];98 }99100// 完全背包问题——优化空间101int BagProblem_complete_optimize(const vector<int> &weight, const vector<int> &value, int n, int v)102 {103 vector<int> dp(v + 1, 0);104105for (int j = 0; j <= v; j++)106 {107 dp[j] = j / weight[0] * value[0];108 }109110for (int i = 1; i < n; i++)111 {112for (int j = 0; j <= v; j++) // dp[j]是由上⼀⾏j列和本⾏⼩于j列推出，因此需要正向枚举113 {114if (j >= weight[i])115 {116 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);117 }118 }119 }120121return dp[v];122 }123124// 多重背包问题125int BagProblem_multi(const vector<int> &weight, const vector<int> &value, const vector<int> &nums, int n, int v) 126 {127 vector<vector<int>> dp(n, vector<int>(v + 1, 0));128129for (int j = 0; j <= v; j++)130 {131int num = min(j / weight[0], nums[0]);132 dp[0][j] = num * value[0];133 }134135for (int i = 1; i < n; i++)136 {137for (int j = 0; j <= v; j++)138 {139if (j < weight[i])140 {141 dp[i][j] = dp[i - 1][j];142 }143else144 {145int num = min(j / weight[i], nums[i]);146for (int k = 0; k <= num; k++)147 {148 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * weight[i]] + k * value[i]);149 }150 }151 }152 }153154return dp[n - 1][v];155 }156157// 多重背包问题——优化空间158int BagProblem_multi_optimize(const vector<int> &weight, const vector<int> &value, const vector<int> &nums, int n, int v) 159 {160 vector<int> dp(v + 1, 0);161162for (int j = 0; j <= v; j++)163 {164int num = min(j / weight[0], nums[0]);165 dp[j] = num * value[0];166 }167168for (int i = 1; i < n; i++)169 {170for (int j = v; j >= 0; j--) // dp[j]是由上⼀⾏<=j列推出，需要逆向枚举171 {172int num = min(j / weight[i], nums[i]);173for (int k = 0; k <= num; k++)174 {175if (j < k * weight[i])176continue;177 dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);178 }179 }180 }181182return dp[v];183 }184185int main()186 {187int v = 10;188int n = 5;189 vector<int> weight{ 2, 2, 4, 6, 3 };190 vector<int> value { 1, 3, 3, 5, 6 };191 vector<int> nums { 1, 2, 3, 4, 1 };192193 cout << BagProblem_01(weight, value, n, v) << endl;194 cout << BagProblem_01_optimize(weight, value, n, v) << endl;195196 cout << BagProblem_complete(weight, value, n, v) << endl;197 cout << BagProblem_complete_optimize(weight, value, n, v) << endl;198199 cout << BagProblem_multi(weight, value, nums, n, v) << endl;200 cout << BagProblem_multi_optimize (weight, value, nums, n, v) << endl;201202return0;203 }。

背包问题是一个经典的动态规划问题，可以使用分支限界法来解决。

以下是一种 C 语言实现：```c#include <stdio.h>#include <stdlib.h>#define MAX_N 100 // 背包物品数量最大值#define MAX_W 1000 // 背包容量最大值// 物品结构体typedef struct {int weight; // 物品重量int value; // 物品价值} Item;int n; // 物品数量int W; // 背包容量Item items[MAX_N]; // 物品数组int max_value; // 最大价值int current_value; // 当前价值int current_weight; // 当前重量// 分支限界法求解背包问题void knapsack(int i) {// 达到根节点或者达到背包容量上限if (i == n || current_weight + items[i].weight > W) {if (current_value > max_value) {max_value = current_value;}return;}// 不选当前物品knapsack(i + 1);// 选当前物品current_weight += items[i].weight;current_value += items[i].value;knapsack(i + 1);current_weight -= items[i].weight;current_value -= items[i].value;}int main() {// 读取输入scanf("%d %d", &n, &W);for (int i = 0; i < n; i++) {scanf("%d %d", &items[i].weight, &items[i].value);}// 初始化max_value = 0;current_value = 0;current_weight = 0;// 求解背包问题knapsack(0);// 输出结果printf("%d\n", max_value);return 0;}```在该实现中，`knapsack` 函数用于递归求解背包问题。

分支界线法01背包问题c语言一、问题描述01背包问题是常见的动态规划问题，其描述如下：有一个背包，最多能承载重量为W的物品。

现在有n个物品，其重量分别为w1, w2, ..., wn，价值分别为v1, v2, ..., vn。

要求选取若干物品放入背包，使得放入背包的物品总价值最大，且总重量不超过W。

二、分支界线法思想分支界线法是一种求解组合优化问题的常用方法。

在01背包问题中，分支界线法的思想是通过一个优先级队列，不断生成和扩展状态空间树，记录每个节点的上界评价函数值，并根据上界值进行搜索剪枝，直至获得最优解。

三、算法步骤1. 定义物品结构体```ctypedef struct {double value; // 物品价值double weight; // 物品重量double unitValue; // 物品单位价值} Item;```2. 比较函数定义（用于优先级队列）```cintpare(const void* a, const void* b) {Item* itemA = (Item*)a;Item* itemB = (Item*)b;double diff = itemB->unitValue - itemA->unitValue; return diff < 0 ? -1 : diff > 0 ? 1 : 0;}```3. 分支界线法求解01背包问题```cdouble knapsack(int n, double W, Item* items) {qsort(items, n, sizeof(Item),pare);double maxValue = 0;double currentWeight = 0;for (int i = 0; i < n; i++) {if (currentWeight + items[i].weight <= W) {currentWeight += items[i].weight;maxValue += items[i].value;} else {double rem本人nWeight = W - currentWeight;maxValue += items[i].unitValue * rem本人nWeight;break;}}return maxValue;}```四、代码实现解释1. 首先根据物品单位价值对物品进行排序，通过单位价值可以快速确定选择哪个物品放入背包；2. 依次选择单位价值最高的物品放入背包，若背包容量不足则按部分放入；3. 根据剩余容量，估算能够放入的最大价值。

#include<iostream>using namespace std;class Knap//建立类knap{friend int Knapsack(int p[],int w[],int c,int n );//友元函数的声明public://共有成员声明void print(){for(int m=1;m<=n;m++){cout<<bestx[m]<<" ";}cout<<endl;};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<=n&&w[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(i>n){if(bestp<cp){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;i<n;i++)for(int j=i;j<n;j++){if(Q[i].d<Q[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;cout<<"请输入背包个数："<<endl;cin>>n;p=new int[n+1];w=new int[n+1];p[0]=0;w[0]=0;cout<<"请输入背包容量："<<endl;cin>>c;cout<<"请依此输入每个物品的重量："<<endl;for(i=1;i<=n;i++)cin>>w[i];cout<<"请依此输入每个物品的价值："<<endl;for(i=1;i<=n;i++)cin>>p[i];cout<<"所能装入背包中总价值最大为"<<Knapsack(p,w,c,n)<<endl; }。