01背包问题/Ieee全球极限编程大赛11.0题BeetleBag题解/洛谷P1926 小书童——刷题大军题解

基础01背包问题

概述

给出一个容积为V的背包，有i个物体，每个物体都有自己的体积和价值，用Vi和Wi表示，要将这些物体装进背包里面，问怎样才能使得装入物体的总价值最大？最大为多少？

解决思路

1.如果你没能正确理解这道题，尤其是对于很多新手，第一反应可能是将所有物体的单位价值算出来，然后按从大到小排序，将单位价值高的物体优先放入背包······

我们来举个例子：现在你的背包体积为10，现在有4个物体，体积分别为1,3,5,7，价值分别为1,4,15,18；如果按单位价值来算15/5>18/7>4/3>1/1,所以现将体积为5的物体放入背包，那么接下来就只能依次放入体积为3和1的物体，这样的话总价值为20，但是显然放入体积为7和3的物体，总价值为22是最大的，那么这种放的方式怎么用算法表示出来呢？

2.算法思路：根据动态规划解题步骤（问题抽象，建立模型，寻找约束条件，判断是否满足最优解原理，找大问题与小问题的递推关系式，填表，寻找解组成）找出01背包问题的最优解及解组成，然后编写代码实现。动态规划其实就是把大问题拆解成一个个的小问题，通过寻找大问题与小问题的递推关系，解决一个个的小问题，最终达到解决大问题的效果，且动态规划的优点在于填表（具有记忆性），可以理解成表中记录每个局部最优然后最终得到全局最优。

3.什么是填表：就是依次将背包容积从1开始递增，记录每一个容积下的最优解，然后通过该最优解推导下一个容积的最优解。这就涉及到一个嵌套循坏了，不仅要将体积从1开始递增，还需要将物体从第一个开始递增，即：将第一次循环只考虑第一个物体，遍历所有的容积，天第一行表，第二次循环考虑前两个物体，遍历所有体积，填第二行表·····（有多少个物体就填多少行表，一共有背包的总容积V列 ，每一行都从体积为1开始填一直到体积为V）

4.大问题与小问题的递推关系式：若有n个物体，背包总容积为m,由上述分析可知这个表应该为n*m（实际上要为(n+1)*(m+1)因为要初始化边缘行列为0），用dp[i][j]来表示该表的第i行第j列(表示考虑放前i个物体且背包容量为j时的最大放入价值)

对于每一个dp[i][j]每次就只需要考虑两种情况：

①背包体积不够放入第i个物体，则dp[i][j]=dp[i-1][j];

②背包体积足够放入第i个物体，但是放入之后剩余体积就变小了，所以需要联系上一行体积相同时的最大价值再加上i的价值和dp[i-1][j]进行比较，

即：dp[i][j]=max(dp[i-1][j],dp[i-1][j-Vi]+Wi)

5.最优解回溯：

①dp[i][j]=dp[i-1][j]时，说明没有选择第i个物体，则回到dp[i-1][j]；

②dp[i][j]=dp[i-1][j-Vi]+Wi时，说明选择了第i个物体，该物体是最优解的组成部分，随后我们回到选择该物体之前，即dp[i-1][j-Vi]；

③一直遍历到i=0结束为止，所有组成的解都会被找到

例题1：Ieee全球极限编程大赛11.0题BeetleBag

题目：

Beetleman joined the Strangers, a team of super heroes who protect cyber world.

In order to increase Beetleman's fighting power, Copperman allowed Beetleman to choose gadgets from his labs freely.

However, Beetleman has limited space in his hero bag.

Your task is to help Beetleman choose gadgets to increase his fighting power as much as possible.

Standard input

The first line of input has one integer tt (1≤t≤251≤t≤25), the number of test cases that will follow.

For each tt there will be a line that contains two integers, number cc (1≤c≤5001≤c≤500), the capacity of Beetleman's bag, and number nn (1≤n≤2001≤n≤200), the number of gadgets in Copperman labs.

Then for each above line, there will be nn lines that will contain two integers, the number ww (1≤w≤1001≤w≤100), the gadget's weight and the number ff (1≤f≤1 0001≤f≤1000), the fighting power of the gadget.

Standard output

Output will have tt lines containing the maximum fighting power from Copperman's gadgets that can fit into Beetleman's bag.

Constraints and notes

• 1≤t≤251≤t≤25
• 1≤c≤5001≤c≤500
• 1≤n≤2001≤n≤200
• 1≤wi≤1001≤wi​≤100 for 1≤i≤n1≤i≤n
• 1≤fi≤1 0001≤fi​≤1000 for 1≤i≤n1≤i≤n

2
6 2
1 17
6 15
5 5
1 1
2 2
3 3
4 4
5 5

17
5

代码：

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

int findx(int c,int n,const vector<vector<int> >& s){
	vector<vector<int> >dp(n+1,vector<int>(c+1,0));
	for(int i=1;i<=n;i++){
		for(int x=1;x<=c;x++){
			if(x<s[i-1][0])dp[i][x]=dp[i-1][x];	
			else{
				dp[i][x]=max(dp[i-1][x],dp[i-1][x-s[i-1][0]]+s[i-1][1]);
			}
		}
	}
	return dp[n][c];
}

int main(){
	int t;
	cin>>t;
	vector<int>result(t);
	int c,n;
	for(int i=0;i<t;i++){
		cin>>c>>n;
		vector<vector<int> >p(n+1,vector<int>(2,0));
		for(int z=0;z<n;z++){
			cin>>p[z][0]>>p[z][1];
		}
		result[i]=findx(c,n,p);
	}
	for(int i=0;i<t;i++){
		cout<<result[i]<<endl;
	}
	return 0;
}

例题2：洛谷P1926 小书童——刷题大军（P1926 小书童——刷题大军 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）

题目：

题目描述

小 A “刷题”十分猖狂，明目张胆地“刷题”。他现在在小书童里发现了 nn 样他喜欢的“题目”，每“题”都有他的需要时间，而老师布置了 mm 项作业，每项作业都有它的需要时间及分值，老师规定 kk 分以上算及格。小 A 只剩 rr 个单位时间，他想在及格的基础上更多地“刷题”。

输入格式

第一行四个整数 n,m,k,rn,m,k,r。

第二行有 nn 个数，代表每“题”他的需要时间。

第三行有 mm 个数，表示每项作业它的需要时间。

第四行有 mm 个数，代表每项作业它的分值。

输出格式

一个数，代表小 A 能刷几道题。

输入输出样例

输入 #1复制

3 4 20 100
15 20 50
10 15 40 40
5 5 10 15

输出 

2

说明/提示

数据范围及约定

对于 100%100% 的数据，n≤10n≤10，m≤10m≤10，k≤50k≤50，r≤150r≤150。数据保证没有不能及格的情况。

代码：

//数学是火，点亮物理的灯；物理是灯，照亮化学的路；化学是路，通向生物的坑；生物是坑，埋葬学理的人。
//文言是火，点亮历史宫灯；历史是灯，照亮社会之路；社会是路，通向哲学大坑；哲学是坑，埋葬文科生。 
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
	int n,m,k,r;
	cin>>n>>m>>k>>r;
	vector<int> N(n+1,0);
	vector<int> MT(m+1,0);
	vector<int> MF(m+1,0);
	for(int i=1;i<=n;i++){
		cin>>N[i];
	}
	for(int i=1;i<=m;i++){
		cin>>MT[i];
	}
	for(int i=1;i<=m;i++){
		cin>>MF[i];
	}
	vector<vector<int> >dp(m+1,vector<int>(r+1,0));
	int cont=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=r;j++){
			if(j<MT[i])dp[i][j]=dp[i-1][j];
			else{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-MT[i]]+MF[i]);
			}
			if(dp[i][j]>=k && i==m){
				cont=r-j;
				break;
			}
		}
		if(cont!=0)break;
	}
	sort(N.begin()+1,N.end());
	int result=0;
	for(int i=1;i<=n;i++){
		if(cont>=N[i]){
			result++;
			cont-=N[i];
		}	
		else break;
	}
	cout<<result<<endl;
	return 0;
}

交流讨论

以上均为个人粗浅见解，若有错误和改进之处，欢迎在评论区交流讨论

若代码有不清楚或者改进之处，也欢迎留言！