动态规划——01背包问题——解法3

动态规划——01背包问题——解法3

题目：这里有n个宝石，每个宝石都有对应的质量和价值，有一个有限容量的背包，大小为m，求怎样放宝石才能使背包价值总和最大

2<=n<=100

1<=m<=10000   

#include 
using namespace std;
int w[101],c[101],f[10001];
int main(){
	int m,n;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> w[i] >> c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			if(j>=w[i]){
				f[j]=max(f[j],f[j-w[i]]+c[i]);
			}
		}
	}
	cout << f[m];
	return 0;
	
	
}

题解：先将宝石的质量（w）和价值（c）分别存入 c 和 w 数组中 在创建一个二维数组 p 行为解锁宝石的数量，列为背包的空间，判断背包能否装下宝石，能装下就比较装宝石（p[i-1][j-w[i]]+c[i]）和不装宝石（p[i-1][j]）哪个价值更高，如果装不下就直接赋值为不装宝石的价值 p[i][j]=p[i-1][j]   最后输出第 n 行 m 列的结果

易错点：1、在计算p[i][j]时的情况要分类讨论，分为 装不下 和 装的下 来讨论