背包问题

0/1背包问题

题目：

• 给定n种物品和一个容量为c的背包，物品i的重量是 wi，其价值为vi。问︰应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大?

问题分析：

• 面对每个物品，我们只有选择拿或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。
• 0/1背包问题中的0代表这个物品不拿，1代表这个物品拿。是一个拿与不拿的问题。

例题及输入输出：

例题的动态规划（DP）

例题代码

//0/1背包问题 
#include<stdio.h> 
#include<stdlib.h>
int dp[35][205];
int w[35],c[35];

int max(int a,int b)
{
	if(a>=b){
		return a;
	}
	return b;
}

int main()
{
	int i=0,j=0;
	int m,n;//m代表背包容量，n代表物品数量 
	printf("请输入m和n的值：\n");
	scanf("%d",&m);
	scanf("%d",&n);
	for(i=1;i<=n;i++){//键盘输入物品重量的数组 
		scanf("%d",&w[i]);
	} 
	for(i=1;i<=n;i++){//键盘输入物品价值的数组 
		scanf("%d",&c[i]);
	} 
	//dp表的计算算法部分 
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(j<w[i]){
				dp[i][j]=dp[i-1][j];
			}else{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
			}
		}
	}
	//输出dp表 
	printf("dp表如下所示:\n");
	for(i=0;i<=n;i++){
		for(j=0;j<=m;j++){
			printf("%-3d",dp[i][j]);
		}
		printf("\n");
	}
	
	printf("背包能放入的最大价值为：%d\n",dp[n][m]);
	return 0;
}

完全背包问题

例题及输入输出：

例题的动态规划（DP）

例题代码

//完全背包问题
//化简前写法 
#include<stdio.h>
#include<stdlib.h>

int w[50],c[50],dp[210]; 

int max(int x,int y)
{
	if(x>y){
		return x;
	}
	return y;
}

int main()
{
	int m,n;
	int i=0,j=0,k=0;
	printf("请输入m和n的值:\n");
	scanf("%d",&m);
	scanf("%d",&n);
	printf("请输入w[i]数组的值:\n");
	for(i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	printf("请输入c[i]数组的值:\n");
	for(i=1;i<=n;i++){
		scanf("%d",&c[i]);
	}
	for(i=1;i<=n;i++){
		for(j=m;j>=1;j--){
			for(k=0;k<=j/w[i];k++){
				dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i]);
			}
		}
	}
	
	printf("%d",dp[m]);
	return 0;
} 

多重背包问题

题目：

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

问题分析：

• 我们仔细观察题目，会发现不同点在于每种物品的数量，01背包是每种只有1件，完全背包是每种无限件，而多重背包是每种有限件。

例题及输入输出：

例题代码

#include<stdio.h>
#include<stdlib.h> 

int max(int x,int y)
{
	if(x>y){
		return x;
	}
	return y;
}

int v[510],w[510],s[510],dp[6100];//v数组代表价格，w数组代表价值，s数组代表数量 

int main()
{
	int n,m;
	int i,j,k;
	printf("请输入n和m的值:\n");
	scanf("%d",&n);
	scanf("%d",&m);
	for(i=1;i<=n;i++){
		scanf("%d",&v[i]);
		scanf("%d",&w[i]);
		scanf("%d",&s[i]);
	}
	
	for(i=1;i<=n;++i){
		for(j=m;j>=1;--j){
			for(k=0;k<=s[i]&&k*v[i]<=j;++k){
				dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
			}
		}
	}
	
	printf("%d",dp[m]);
	
	return 0;
} 

背包问题系列

原文：https://www.cnblogs.com/rosy1203/p/15114213.html