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

0%

Bone Collector(01背包)

发表于 更新于 分类于 ，   |   字数统计: 717(字)   |   阅读时长: 3(分) Valine：

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

题目

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

![HDU](1jpg %}

输入格式

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

输出格式

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

输入样例

1
2
3
4
1 
5 10 
1 2 3 4 5 
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]);

![二维数组的动态图](2jpg %}

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

一维数组

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

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

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