c语言背包问题C语言 背包问题

背包问题，C语言编程

原始题目： 有N件物品和一个容量为V的背包。

第i件物品的费用是c[i]，价值是 w[i]。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容 量，且价值总和最大。

（取自百度百科） 问题简化： 1. 背包可容纳总重量为M 2. 有n个物品，每个重量为m[0]. m[1]. m[2] ......m[i] 对应每个物品的 价值为s[0]. S[1]. S[2]....s[i] (i<=n) 3. 放入第i个物品,比较m[i]和M的大小,不超过M则记录下当前价值s 4. 最终取得最大值s 实现方法： 定义三个浮点型一维数组float m[[n]和s[n]和y[n] 定义float M,float a,b定义int n,j, int i 请输入背包容量大小M： please input the number of the things： please input the value of the things： 把输入数据按顺序分别定义到数组中（若可以的话，把m[n]的数据由小到大排序，判断最小值m[0]和M的大小，若m[0]>M，输出error） 创建一个栈（这里的东西不太懂—-—） 将第一个数据压入栈底,定义i=0，把当前的m[i]赋值给a，s[i]赋值给b,把当前i存放进数组y[n]，以后在每次比较过程中，都把较大b值所对应的物品数存放进y[n]中 判断a<M（这里，若在4已经做过，则可省略，第一个数据一定小于M） 判断a+m[++i]<=M，为真，把第i（注意，此时i已经自增了，这个i是数组中的下标）个数据压入栈，赋值a=a+m[++i]，比较b和b+s[++i]的大小，赋值b=b+s[++i]（理论上，物品价值总该是为正的吧，若是这样的话，不用比较大小了，直接赋新值，直到跳出第一轮循环为止；另外有一种设想，若价值全为正，可以转而把问题这样简化：即给定容量大小和全为正的价值物品，现在想办法让背包放入物品的数量最多 就行了）；若为假，转10 如此进行一轮循环，直到出现10，此时b为一轮循环的最大值，return b,y[n] 当a+m[++i]>M，从栈中弹出m[i-2]，a=a-m[i-2],,当i原本就小于等于2的时候，则清除栈中数据，转12，判断a+m[i]<=M，为真，比较b和b-s[i-2]+s[i]，并把较大值赋给b，继续向下比较，这时候就不用压入栈中了,再定义一个j=1 判断a+m[i+j]<=M,为真，比较b和b-s[i-2]+s[i+j]大小，较大值赋给b，为假，从栈中弹出m[i-3]，当i原本就小于等于3的时候，则清除栈中数据，转12，判断a+m[i]<=M，为真，比较b和b-s[i-3]+s[i]（注意，这个b一直在被赋予最新值），如此进行第一轮循环，用for语句实现，因为下面还有嵌入 此时栈中没有数据，并且，已经把m[0]为栈底的循环计算完毕，现在开始计算m[1]为栈底的循环，在这一循环，忽略掉m[0]，所有可能情况已经在8-11计算过 依此往下，直到栈底被压入的是m[n]为止，计算完毕，输出b，并且输出数组y[n] 碰巧帮同学，也是这个问题，希望能帮助你。

C语言程序设计 背包问题

#include<stdio.h> #define N 100 int n,limitW,totV,maxV; int option[N],cop[N] = {0}; struct { int weight; int value; }a[N]; void find(int i,int tw,) { int k; if(tw + a[i].weight <= limitW) { if(i < n - 1) find(i + 1,tw + a[i]); else { for(k = 0;k < n;k++) option[k] = cop[k]; maxV =; } } - a[i].value > maxV) { if(i < n - 1) find(i + 1, - a[i].value); else { for(k = 0;k < n;k++) option[k] = cop[k]; maxV = - a[i].value; } } } int main() { int i,k,w,v; printf("输入物品总数 : "); scanf("%d",&n); for(i = 0; i < n;i++) { printf("第%d/%d件物品的重量和价值 : ",i + 1,n); scanf("%d %d",&a[i].weight,&a[i].value); } printf("输入限制重量 ："); scanf("%d",&limitW); maxV = 0; totV = 0; find(0,0,totV); for(k = 0;k < n;k++) if(option[k]) printf("%4d",k + 1); printf(" 最大总值为%d ",maxV); return 0; }

C语言动态规划之背包问题求解

#include<stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { //int max(int , int ); int n,m,i,j; int data[101][2]; int f[101][101]; scanf("%d%d",&n,&m); //n表示个数，m表示能背的最大重量 for(i=1;i<=n;i++) { scanf("%d%d",&data[i][0],&data[i][1]); } //我是数组从第一个开始记得，看着容易理解，没必要去省那么几B的内存 for(i=0;i<=m;i++) f[0][i]=0; for(i=0;i<=n;i++) f[i][0]=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { f[i][j]=0; if (j>=data[i][0]) { f[i][j]=max(f[i-1][j],f[i-1][j-data[i][0]]+data[i][1]); //对于这件物品要么不选要么选，不选是f[i-1][j]; //选的话为f[i-1][j-data[i][0]]此处j-data[i][0]是因为要选上一次就得少背j-data[i][0]的重量 //才能装下这次的物品 } else f[i][j]=f[i-1][j]; } printf("%d ",f[n][m]); return 0; } 然后常见的背包问题还有多重背包问题，对于每一个物品可能有多个这种可以预处理成一般的背包问题，就是把几个摊开，很简单就不解释了，当然也可以加一维. 还有就是完全背包问题他的状态转移方程是f[i,j]=max(f[i-1][j],f[i][j-data[i].v]); 他和01的区别只是要选的时候不是f[i-1][j-data[i].v]而是f[i][j-data[i].v]，这样就能选到自己了，如果是初学可能不好理解，慢慢理会吧，其实这个很妙，我当初用了很多种方法，都是错的，看了一时也没明白，后来豁然开朗，然后对动规的理解都上了一个层次. 还有就是多为背包，这个只需要加一维，理解了前面的自然就能做出来了，根本不需要再看状态转移方程了（事实上理解后01就能够做出来了）. 一句话：要多思考，反复思考 我很久没碰算法了，我没现成的代码这是我手打出来的，求分

求【背包问题】【C语言】【递归算法】的重要代码注释【最好每行都注释】【附源代码】【O(∩_∩)O谢谢】

这个算法厉害。

#include "stdafx.h" #include <iostream> using namespace std; #define N 7//物品数量 #define S 20//要求背包重量 int W[N+1]={0,1,4,3,4,5,2,7};//各物品重量，W[0]不使用。

。

。

int knap(int s,int n)//s为剩余重量，n为剩余可先物品数。

。

{ if(s==0)return 1;//return 1 means ess.. if(s<0||(s>0&&n<1))return 0;//如果s<0或n<1则不能完成 if(knap(s-W[n],n-1))//从后往前装，如果装满第n个包，剩余的重量仍然可以在剩余的n-1包中放下，那么就将第n个包装满。

{ printf("%4d",W[n]);//打印第n个包的容量，即装进第n个包的重量。

return 1; } return knap(s,n-1);//如果装满第n个包后，剩余的重量不能在剩余的n-1包中放下，那么就不用第n个包，考虑能不能用第n-1个包。

} void main() { if(knap(S,N))printf(" OK! "); else printf("Failed!"); }

C语言 背包问题

这个答案是我在网上找到的，你自己看看吧 0/1背包经典问题： 需对容量为M的背包进行装载。

从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。

对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。

约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。

我的程序：思想——动态规划法，先考虑没有物品要放的时候S0，再考虑只有一个要放物品a的各种情况S1，再综合考虑只有第一个a和第二个b物品要放时的情况S2，再综合考虑有三个待放物品abc的情况…… #include<stdio.h> #include<iostream.h> #define MAX 200 void main(void) { cout<<"******************************************************"<<endl <<"******************* 0/1背包问题 ***************"<<endl <<"******************* CopyRight: ***************"<<endl <<"******************* Grace Air ***************"<<endl <<"******************************************************"<<endl; int n,M; int num,t,q; int temp; int s[100]; int x[100];//决策集 int ww,pp,i,j,k,r,next; int u;//记录附加结点 int P[100000],W[100000];//存放所有的可行序偶 P[0]=W[0]=0;//S0中的点(0，0) int F[100];//记录si点的起点在P[]W[]数组中的位置 F[0]=0;F[1]=next=1; int begin,end;begin=end=0; int wi[100],pi[100],w[100],p[100]; cout<<"请输入下列背包初始信息:"<<endl; cout<<endl<<"背包最大容量为："; cin>>M; cout<<endl<<"请输入下列物品初始信息:"<<endl; cout<<endl<<"物品种类有几种？："; cin>>n; for(num=0;num<n;num++) { cout<<endl<<"第"<<num+1<<"种物品重量："; cin>>wi[num]; cout<<" 价值："; cin>>pi[num]; } for(num=0;num<n;num++) { temp=wi[0]; q=0; for(t=0;t<n;t++) { if(temp>wi[t]) { temp=wi[t]; q=t; } } s[q]=num+1; w[num]=wi[q]; p[num]=pi[q]; wi[q]=MAX; } for(i=0;i<n;i++) { F[i+1]=end+1; u=begin;//从头开始考虑序偶点 for(r=begin;r<end+1;r++)//生成sii图，s1中只考察结点0, { if(W[r]+w[i]<=M) u=(W[r]+w[i])>(W[u]+w[i])?r:u;//s1的u=0,u是sii中能让i结点加上它把空间塞得最满的那个结点，即 //造成s12中x轴最向右靠近确定的M值的点的附加点 }//u号以前的点都是可以考虑加入的点 k=begin;//k是记录si-1图中已加入到si图中的点 for(j=begin;j<u+1;j++)//生成si图 { ww=W[j]+w[i]; pp=P[j]+p[i]; while(k<=end&&W[k]<ww)//将si-1的点都加到si中 { P[next]=P[k]; W[next]=W[k]; next++;k++; } if(k<=end&&W[k]==ww) { pp=pp>P[k]?pp:P[k]; k++; } if(pp>P[next-1])//sii中的点如果效益比以前的大，加进si { P[next]=pp; W[next]=ww; next++; } while(k<=end&&P[k]<=P[next-1]) k++; } begin=end+1; end=next-1; } //回溯 int PX,WX,PY,WY; PX=P[end];WX=W[end]; for(i=n;i>0;i--) { PY=P[F[i]-1];WY=W[F[i]-1]; if(PX>PY) { x[i]=1; PX=PX-p[i-1];WX=PY-w[i-1]; } else x[i]=0; } cout<<endl<<"最优决策为："; for(i=0;i<n;i++) cout<<x[s[i]]<<" "; cout<<endl<<"最优效益为:"<<P[end]<<endl<<"重量："<<W[end]<<endl; }