Life has its own fate, and meeting may not be accidental.

0%

Bone Collector(01背包)

之前背包问题学了忘学了忘= =是太笨了。

题目

许多年前,在泰迪的家乡,有一个人被称为“骨收集者”。这个人喜欢收集各种骨头,例如狗,牛的骨头,他也去了坟墓……
骨头收集者有一个大袋子,里面装有V,而且在收集骨头的过程中,很明显,不同的骨骼具有不同的值和不同的体积,现在给定沿途的每个骨骼的值,您能否计算出骨骼收集器可以获得的总值的最大值?

HDU

输入格式

第一行包含整数T,即案例数。紧随其后的是T个案例,每个案例三行,第一行包含两个整数N,V(N <= 1000,V <= 1000),它们表示骨头的数量和包的体积。第二行包含代表每个骨骼值的N个整数。第三行包含N个整数,代表每个骨骼的体积。

输出格式

每行一个整数,代表合计的最大值(该数字将小于2 [sup] 31 [/ sup])。

输入样例

1
1 
2
5 10 
3
1 2 3 4 5 
4
5 4 3 2 1

输出样例

14

二维数组

问题分解:当前最优解,要么包含第i种物品,要么不包含第i种物品。
DP[i][j]表示前i个物品,背包容量为j的最优值。
状态转移方程为:DP[i][j] = max(DP[i-1][j], DP[i-1][j-v[i]] + w[i]);

二维数组的动态图

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,m,t;
4
int dp[1100][1100],w[1100],v[1100];
5
int main(){
6
	scanf("%d",&t);
7
	while(t--){
8
		memset(dp,0,sizeof(dp));
9
		scanf("%d %d",&n,&m);
10
		for(int i=1;i<=n;i++) scanf("%d",&w[i]);		//骨骼值 
11
		for(int i=1;i<=n;i++) scanf("%d",&v[i]);		//体积 
12
		for(int i=1;i<=n;i++){
13
			for(int j=0;j<=m;j++){
14
				if(j>=v[i])
15
					dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
16
				else
17
					dp[i][j]=dp[i-1][j];		//保留之前的状态 
18
			}
19
		}
20
		printf("%2d ",dp[n][m]);
21
	}
22
	return 0;
23
}

一维数组

和二维数组的差不多,不过就是把二维保存的值放到一维数组中
状态转移方程dp[j]=max(dp[j],dp[j-v[i]]+w[i]);,保证每轮和上轮可以用的比,保证3比2,2比1。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,m,t;
4
int dp[1100],w[1100],v[1100];
5
int main(){
6
	scanf("%d",&t);
7
	while(t--){
8
		memset(dp,0,sizeof(dp));
9
		scanf("%d %d",&n,&m);
10
		for(int i=0;i<n;i++) scanf("%d",&w[i]);     //骨骼值
11
		for(int i=0;i<n;i++) scanf("%d",&v[i]);     //体积
12
		for(int i=0;i<n;i++){
13
			for(int j=m;j>=v[i];j--){       
14
				dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
15
			}
16
		}
17
		printf("%d\n",dp[m]);
18
	}
19
	return 0;
20
}

如果有说错的地方,欢迎指错~~