0-1背包问题

亦凉 2022-08-08 13:59 156阅读 0赞

有n个物体，重量和价值已知，要放入容量为c的背包里，放入的时间，要求放入的总重量不能超过包的容量，同时保证价值最大。

动态规划：

#include <stdio.h>
 
 #define min(a,b) a>b?b:a
 #define max(a,b) a>b?a:b
 
 int main()
 {
 int n,c;
 int *w, *v,*flag; //w代表每个物品的容积，v代表价值, flag代表是否出现
 int **m; //m[i,j]用来存储当剩余容量为j时，可选择的物品为i,i+1,...时，0-1背包问题的最优值
 int i,j,k;
 int jMax; 
 
 printf("please input the number of things and the volume of the knap:");
 scanf("%d %d",&n,&c);
 
 w=new int [n];
 v=new int [n];
 flag=new int [n];
 
 m=new int *[n];
 for(i=0;i<n;i++)
 m[i]=new int [c+1];
 
 printf("input the volume of each thing:");
 for(i=0;i<n;i++)
 scanf("%d", &w[i]);
 
 printf("input the value of each thing:");
 for(i=0;i<n;i++)
 scanf("%d",&v[i]);
 //从最后一个元素倒着推导，即第n-1个元素
 jMax=min(w[n-1]-1,c);
 for(j=0;j<=jMax;j++)
 m[n-1][j]=0;
 for(j=w[n-1];j<=c;j++)
 m[n-1][j]=v[n-1];
 for(i=n-2;i>0;i--)
 {
 jMax=min(w[i]-1,c);
 for(j=0;j<jMax;j++)
 m[i][j]=m[i+1][j];
 for(j=jMax;j<=c;j++)
 m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
 }
 m[0][c]=m[1][c];
 if(c>=w[0]) 
 m[0][c]=max(m[1][c],m[1][c-w[0]]+v[0]); 
 printf("the max value is %d. and the concrete are:\n",m[0][c]);
 for(i=0;i<n-1;i++)
 {
 if(m[i][c]==m[i+1][c]) 
 flag[i]=0;
 else
 {
 flag[i]=1;
 c=c-w[i];
 }
 flag[n-1]=(m[n-1][c])?1:0;
 }
 for(i=0;i<n;i++)
 if (flag[i])
 printf("%d ",v[i]);
 printf("\n");
 return 0;
 }

回溯法：

#include<stdio.h>
 
 int*w,*v,weigt,n,sumW,bestV,tempV;
 void backtrack(int t)
 {
 if(sumW<=weigt)
 {
 int i;
 if(t>n)
 {
 for(i=0;i<n;i++)
 {
 if(tempV>bestV)
 bestV=tempV;
 }
 }else
 {
 sumW+=w[t];
 tempV+=v[t];
 backtrack(t+1);
 sumW-=w[t];
 tempV-=v[t];
 backtrack(t+1);
 }
 }
 }
 
 int main()
 {
 int i;
 printf("Please enter the space of the backpack:");
 scanf("%d",&weigt);
 
 printf("Please input the number of objects:");
 scanf("%d",&n);
 w=new int[n];
 v=new int[n];
 
 printf("Please input the weigt of each object:\n");
 for(i=0;i<n;i++)
 scanf("%d",w+i);
 
 printf("Please input the value of each object:\n");
 for(i=0;i<n;i++)
 scanf("%d",&v[i]);
 
 sumW=0;
 tempV=0;
 bestV=0;
 backtrack(0);
 printf("%d\n",bestV);
 return 0;
 }

分支限界法：

#include <stdio.h>
 #include <stdlib.h>
 
 typedef struct QNode{
 int value; //当前结点的总价值
 int weight; //当前的总重量
 struct QNode *next;
 }QNode, *QueuePtr;
 
 typedef struct{
 QueuePtr front;
 QueuePtr rear;
 }Queue;
 
 int initQueue(Queue &Q){
 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
 if(!Q.front)
 return -1;
 Q.front->next=NULL;
 return 1;
 }
 
 int emptyQueue(Queue Q){
 if (Q.front==Q.rear)
 return 1;
 else
 return 0;
 }
 
 int destroyQueue(Queue &Q){
 while(Q.front){
 Q.rear=Q.front->next;
 free(Q.front);
 Q.front=Q.rear;
 }
 return 1;
 }
 
 int enQueue(Queue &Q, int value, int weight){
 QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
 if(!p)
 return -1;
 p->value=value; 
 p->weight=weight; 
 p->next=NULL;
 Q.rear->next=p;
 Q.rear=p;
 return 1;
 }
 
 int deQueue(Queue &Q, int &value, int &weight){
 QueuePtr p;
 if(Q.front==Q.rear)
 return -1;
 p=Q.front->next;
 value=p->value;
 weight=p->weight;
 Q.front->next=p->next;
 if(Q.rear==p) 
 Q.rear=Q.front;
 free(p);
 return 1;
 }
 
 Queue loadingQueue;
 int bestvalue, n;
 
 void inQueue(int value, int weight, int i)
 {
 if(i==n-1){
 if(value>bestvalue)
 bestvalue=value;
 }
 else
 enQueue(loadingQueue,value,weight);
 }
 int main(){
 int i,j,k;
 int *w, *v, ew, ev;
 int c;
 printf("input the number of things and the volume of ships:");
 scanf("%d%d",&n,&c);
 w=new int[n];
 v=new int[n];
 printf("input the weights:");
 for(i=0;i<n;i++)
 scanf("%d",&w[i]);
 printf("input the values:");
 for(i=0;i<n;i++)
 scanf("%d",&v[i]);
 initQueue(loadingQueue);
 enQueue(loadingQueue,-1,0); 
 i=0; //层数
 ew=0; //扩展结点对应的载重量
 ev=0; 
 while(true){
 if(ew+w[i]<=c)
 inQueue(ev+v[i],ew+w[i],i);
 inQueue(ev,ew,i);
 deQueue(loadingQueue, ev,ew);
 if(ev==-1) //同层结点尾部{ 
 if(emptyQueue(loadingQueue)){
 printf("the result is %d.\n",bestvalue);
 break;
 }
 enQueue(loadingQueue,-1,0);
 deQueue(loadingQueue, ev,ew);
 i++;
 }
 } 
 return 0;
 }

暴力搜索：

#include <stdio.h>
 #include <math.h>
 
 int main()
 {
 int num,maxv=0;
 int n, c, *w, *v, tempw, tempv;
 int i,j,k;
 
 scanf("%d%d",&n,&c);
 
 w=new int [n];
 v=new int [n];
 
 for(i=0;i<n;i++)
 scanf("%d",&w[i]);
 
 for(i=0;i<n;i++)
 scanf("%d",&v[i]);
 
 for(num=0;num<pow(2,n);num++) //每一个num对应一个解
 {
 k=num; tempw=tempv=0; 
 for(i=0;i<n;i++) //n位二进制
 {
 if(k%2==1){ //如果相应的位等于1，则代表物体放进去，如果是0，就不用放了
 tempw+=w[i];
 tempv+=v[i];
 }
 k=k/2; //二进制转换的规则
 }
 //循环结束后，一个解空间生成，
 //判断是否超过了背包的容积，
 //如果没有超，判断当前解是否比最优解更好
 if(tempw<=c){
 if(tempv>maxv)
 maxv=tempv;
 }
 }
 
 printf("%d\n",maxv);
 
 return 0; 
 }