25.3.7刷题

P1049 装箱问题

https://www.luogu.com.cn/problem/P1049

题解

将每个物品的体积当作价值，就转换成了01背包。最后输出背包容量-最大价值（即最大体积）。

#include<bits/stdc++.h>
using namespace std;

const int N = 20010;
int v[N];
int dp[N];
int n,m;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> v[i];
		for (int j = n; j >= v[i]; j--)
		{
			dp[j] = max(dp[j], dp[j - v[i]]+v[i]);
		}
	}

	cout << n - dp[n];
	return 0;
}

P1757 通天之分组背包

https://www.luogu.com.cn/problem/P1757

题解

分组背包模板，记录下输入和分组数，剩下背模板

#include<bits/stdc++.h>
using namespace std;

const int N = 1010, M = 110;
int a, b, c;
int n, m;
int v[N][N], w[N][N];
int cntc[N];
int dp[N];
int k;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> m >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a >> b >> c;
		cntc[c]++;
		v[c][cntc[c]] = a;
		w[c][cntc[c]] = b;
	}

	for (int i = 1; i <= n; i++)
	{
		if (cntc[i] != 0) k++;
	}

	for (int i = 1; i <= k; i++)
	{
		for (int j = m; j >= 0; j--)
		{
			for (int k = 1; k <= cntc[i]; k++)
			{
				if (v[i][k] <= j)
				{
					dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
				}
			}
		}
	}

	cout << dp[m];

	return 0;
}

P1832 A+B Problem(再升级)

https://www.luogu.com.cn/problem/P1832

题解

线性筛法，筛出质数。转换成完全背包问题，每个素数可以无限选，背包容量为n。

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int primes[N], cnt;
bool st[N];

int n;
long long  dp[N];//需要开long long 

void get_primes(int n)//线性筛法
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i]) primes[cnt++] = i;
		for (int j = 0; primes[j] <= n / i; j++)
		{
			st[primes[j] * i] = true;
			if(i%primes[j]==0) break;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	get_primes(n);


	dp[0] = 1;
	for (int i = 0; i < cnt; i++)//素数个数
	{
		for (int j = primes[i]; j <= n; j++)
		{
			dp[j] +=dp[j-primes[i]];//选上这个素数的方案数+=不选这个素数的方案数
		}
	}
	cout << dp[n];

	return 0;
}