一、01背包问题 

问题描述：

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

       所谓01背包，表示每一个物品只有一个，要么装入，要么不装入。

测试数据： 

有一个背包体积为10，有6件物品：

解题报告图解：

代码：

#include
    
     #define max(x,y)	x>y?x:yint c[100];int w[100];int f[100][100]={0};int main(){	int i,n,v,j;	scanf("%d%d",&n,&v);	for(i=1;i<=n;i++){		scanf("%d%d",&c[i],&w[i]);		for(j=1;j<=v;j++){			if(j>=c[i])	f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);			else f[i][j]=f[i-1][j];			printf("%d ",f[i][j]);		}		printf("\n");	}	return 0;	}
    

以上是01背包模板代码！01背包的纠结点就是，一个物品的放与不放的问题。

二、完全背包问题 

问题描述：

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

       所谓完全背包，表示每一个物品可以取无数件。

测试数据：

同01背包 ↑ _ ↑：

解题报告图解：

代码：

#include
    
     #define max(x,y)	x>y?x:yint c[100];int w[100];int f[100][100]={0};int main(){	int i,n,v,j,d=1;	scanf("%d%d",&n,&v);	for(i=1;i<=n;i++){		scanf("%d%d",&c[i],&w[i]);		int k=v / c[i];		while(k--){			for(j=1;j<=v;j++){				if(j>=c[i])	f[d][j]=max(f[d-1][j],f[d-1][j-c[i]]+w[i]);				else f[d][j]=f[d-1][j];				printf("%d ",f[d][j]);			}			printf("\n");			d++;		}	}	return 0;	}
    

完全背包的代码与01背包的代码如出一辙，其实就是改造了一下下，也就是把完全背包改造成01背包了而已！

三、多重背包问题

请参照完全背包进行改造，改造成01背包就OK了，！如有疑问，请留言喔

版权声明：本文为博主原创文章，未经博主允许不得转载。