动态规划 Part II

大家好，我是wangmy。

众所周知动态规划将原问题分解成若干个子问题，再把子问题分解成若干更多子问题。先求解子问题，再从这些子问题的解得到原问题的解。

今天我给大家分享一下动态规划的几道题和参考代码。

砝码秤重

题目描述(Description)

设有n种砝码,第k种砝码有Ck个,每个重量均为Wk,求：用这些砝码能秤出的不同重量的个数，但不包括一个砝码也不用的情况。

输入格式(Format Input)

输入的第一行只有一个数n,表示不同的砝码的种类数. 第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量.

输出格式(Format Output)

输出中只有一行数据:Total=N。表示用这些砝码能秤出的不同重量数。

输入样例(Sample Input)

2 
2 2
2 3

输出样例(Sample Output)

Total=8

限制(Restrictions)

时间限制(Time Limit):  1000 ms

内存限制(Memory Limit):  65536 KB

说明/提示(Hint)

对于100%的数据,砝码的种类n满足:1≤n≤100;
对于30%的数据,砝码的总数量C满足:1≤C≤20;
对于100%的数据,砝码的总数量C满足:1≤C≤100;
对于所有的数据,砝码的总重量W满足:1≤W≤400000;

参考代码

#include<bits/stdc++.h>
using namespace std;
int n, a[110], cnt, sum;
bool f[400010];
int main()
{
	cin >> n;
	int c, w;
	for(int i = 1; i <= n; i++){
		scanf("%d%d", &c, &w);
		sum += c * w;
		//二进制打包，极大减少打包次数 
		for(int j = 1; c >= j; j <<= 1) {
			a[++cnt] = j * w;
			c -= j;
		}
		if(c) a[++cnt] = c * w;
	}
	f[0] = 1;
	for(int i = 1; i <= cnt; i++){
		//从大到小枚举，保证大状态依赖的小状态未被更新（上一维） 
		for(int j = sum; j >= a[i]; j--)
			if(f[j - a[i]]) f[j] = 1;
	}
	int ans = 0;
	for(int i = 1; i <= sum; i++) if(f[i]) ans++;
	printf("Total=%d", ans);
	return 0;
}

石子归并

题目描述(Description)

有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。

输入格式(Format Input)

输入第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。

输出格式(Format Output)

输出只有一行,该行只有一个整数,表示最小的质量差.

输入样例(Sample Input)

5 
5
8
13
27
14

输出样例(Sample Output)

3

限制(Restrictions)

时间限制(Time Limit):  1000 ms

内存限制(Memory Limit):  65536 KB

参考代码

#include<bits/stdc++.h>
using namespace std;
bool f[55][500010];
int n,a[55],sum;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=sum;j++)
		{
			f[i][j]=f[i-1][j];
			if(j>=a[i]&&f[i-1][j-a[i]])
			{
				f[i][j]=1;
			}
		}
	}
	for(int i=sum/2;i>=0;i--)
	{
		if(f[n][i])
		{
			printf("%d",sum-i-i);
			return 0;
		}
	}
	return 0;
}

补圣衣

题目描述(Description)

有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。

输入格式(Format Input)

本题包含5行数据：
第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 
第2行，为A1...As1 共s1个数，表示第一件衣服上每个破损修好它所需的时间 
第3行，为B1...Bs2 共s2个数，表示第二件衣服上每个破损修好它所需的时间
第4行，为C1...Cs3 共s3个数，表示第三件衣服上每个破损修好它所需的时间
第5行，为D1...Ds4 共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60

输出格式(Format Output)

输出一行,为修好四件衣服所要的最短时间。

输入样例(Sample Input)

1 2 1 3		
5
4 3
6
2 4 3

输出样例(Sample Output)

20

限制(Restrictions)

时间限制(Time Limit):  1000 ms

内存限制(Memory Limit):  65536 KB

参考代码

#include<bits/stdc++.h>
using namespace std;
int s[5], a[25], sum, ans;
bool dp[1210];

int main()
{
	
	for(int i = 1; i <= 4; i++) scanf("%d", &s[i]);
	
	for(int t = 1; t <= 4; t++){
		
		sum = 0;
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= s[t]; i++) scanf("%d", &a[i]), sum += a[i];
		
		dp[0] = 1;
		for(int i = 1; i <= s[t]; i++){
			for(int j = sum; j >= a[i]; j--)
				if(dp[j - a[i]]) dp[j] = 1;
		}
		int mid = sum / 2;
		
		for(int i = mid; i >= 0; i--){
			if(dp[i]){
				ans += sum - i;
				break;
			}
		} 
	}
	cout << ans;
	

	return 0;
}

今天的分享到此结束，我们下次再见。（希望大家有自己的思考，不要一味着抄代码）