knapsack1.cpp

二维背包问题

#include <iostream.h>
#include<iomanip.h>
#include<string.h>

int min(int w,int c)
{int temp;
 if (w<c) temp=w;
 else
 temp=c;
 return temp;
}
int max(int w,int c) //
{
    int temp;
    if (w>c) temp=w;
    else
    temp=c;
    return temp;
}

void knapsack(int v[],int w[],int b[],int n,int c,int d,int***m)      //求最优值
{
	int j=0;
	int k=0;

    int jmax=min(w[n]-1,c);//用于防止物品的性质超出包所能承受的
	int kmax=min(b[n]-1,d);
	for(j=0;j<=jmax;j++){ //只有一个物品可选，且背包承重不足的情况
        for(k=0;k<=d;k++){
		    m[n][j][k]=0;
		}
	}

	for(j=jmax;j<=c;j++){ //只有一个物品可选，背包可承重但空间不够的情况
        for(k=0;k<=kmax;k++){
		    m[n][j][k]=0;
		}
	}

    for(j=w[n];j<=c;j++){ //只有一个物品可选，各条件满足
        for(k=b[n];k<=d;k++){
		    m[n][j][k]=v[n];
		}
	}

    if (n>1) {
	    for(int i=n-1;i>1;i--){ //判断第i个物品是否装入背包
            jmax=min(w[i]-1,c);
	        kmax=min(b[i]-1,d);
            for(j=0;j<=jmax;j++){ //第i个物品的重量超出背包承重
                for(k=0;k<=d;k++){
		            m[i][j][k]=m[i+1][j][k];
				}			
			}

		    for(j=w[i];j<=c;j++){ //第i个物品的体积超出背包容积
                for(k=0;k<=kmax;k++){
		            m[i][j][k]=m[i+1][j][k];
				}
			}

            for(j=w[i];j<=c;j++){//对比物品i装入于不装入的价值大小
                for(k=b[i];k<=d;k++){
		        	m[i][j][k]=max(m[i+1][j][k],m[i+1][j-w[i]][k-b[i]]+v[i]);
				}
			}
		}

	    m[1][c][d]=m[2][c][d];
        if(c>=w[1]&&d>=b[1])
            m[1][c][d]=max(m[1][c][d],m[2][c-w[1]][d-b[1]]+v[1]);
	}
    cout<<"最优值："<<m[1][c][d]<<endl;
}

int traceback(int ***m,int w[],int b[],int n,int c,int d,int x[])      //回代，求最优解
{
    cout<<"得到的一组最优解如下:";

    for(int i=1;i<n;i++){
        if(m[i][c][d]==m[i+1][c][d]) x[i]=0;
            else {
				x[i]=1;
                c-=w[i];
				d-=b[i];
			}
    }
    x[n]=(m[n][c])?1:0;
    for(int y=1;y<=n;y++)
	{
        cout<<setw(5)<<x[y];
	}
    cout<<endl;
    return x[n];
  
}
void main()
{
    int n;//物品数量
    int c;//背包承重
    int d;//背包容积
    int ***m;

    cout<<"&&&&&&&&&&&&&&&&&&&&&欢迎使用二维背包问题程序&&&&&&&&&&&&&&&&&&&"<<endl;
    cout<<"请输入物品个数:";
    cin>>n;

    int *x=new int[n+1];//最优解
    int *v=new int[n+1];//物品价值
    int *w=new int[n+1];//物品重量
    int *b=new int[n+1];//物品体积
 
   
    cout<<"请输入背包承受重量上限:";
    cin>>c;

    cout<<"请输入背包容积:";
    cin>>d;

    cout<<"请输入物品价值 (v[i]):"<<endl;
    for(int i=1;i<=n;i++)
        cin>>v[i];
 
    cout<<"请输入物品重量 (w[i]):"<<endl;
    for(int j=1;j<=n;j++)
        cin>>w[j];

    cout<<"请输入物品体积 (b[i]):"<<endl;
    for(int k=1;k<=n;k++)
        cin>>b[k];

    m=new int**[n+1];  //动态的分配三维数组
    for(int p=0;p<n+1;p++)
	{
        m[p]=new int*[c+1];
        for(int q=0;q<c+1;q++)
		{
            m[p][q]=new int[d+1];
		} 
	} 
 
    knapsack(v,w,b,n,c,d,m);
    traceback(m,w,b,n,c,d,x);

}