《算法竞赛进阶指南》0x52 背包

这篇具有很好参考价值的文章主要介绍了《算法竞赛进阶指南》0x52 背包。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

0x52 背包

数字组合

题意

N N N 个正整数中选出若干数,和为 M M M,询问方案数

解析:

01背包。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, m;
int f[maxn]; 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	f[0] = 1;
	for(int i = 1, v; i <= n; i++){
		cin >> v;
		for(int j = m; j >= v; j--)
			f[j] += f[j-v];
	}
	cout << f[m];
	return 0;
}

自然数拆分

题意:

给定一个数 N N N,将 N N N 拆成若干整数相加的形式。不考虑加数的顺序。至少拆成两个整数

解析:

完全背包。

f i , j f_{i,j} fi,j 为使用前 i i i 个数将 j j j 拆分的方案数,且没有拆成两个数的限制。

因为一个数必须拆成至少两个加数,所以不能将 j j j 拆成 j j j。所以答案为 f n − 1 , n f_{n-1,n} fn1,n

滚掉一维。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll mod = 2147483648;
typedef pair<int, int> pii;

ll f[maxn];
int n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	f[0] = 1;
	for(int i = 1; i < n; i++){
		for(int j = i; j <= n; j++)
			f[j] = (f[j]+f[j-i]) % mod;
	}
	cout << f[n] << endl;
	return 0;
}

陪审团

题意:

n n n 个人,每个人有两个参数 p i , d i p_i,d_i pi,di。从中选出 m m m 个人,使 ∣ D − P ∣ |D-P| DP 最小, D D D 为选出来的人的 d i d_i di 和, P P P 同理。如果方案不唯一,选择 D + P D+P D+P 最大的方案。

解析:

f i , j , k f_{i,j,k} fi,j,k 为在前 i i i 人,选出 j j j 人, D − P = k D-P = k DP=k 的最大的 D + P D+P D+P

k k k 有可能是负数,加上偏移量 b a s e = 400 base = 400 base=400

如果不选第 i i i 个人: f i , j , k = f i − 1 , j , k f_{i,j,k} = f_{i-1, j, k} fi,j,k=fi1,j,k

如果选第 i i i 个人: f i , j , k = f i − 1 , j − 1 , k − d i + p i + d i + p i f_{i,j,k} = f_{i-1, j-1, k-d_i+p_i}+d_i+p_i fi,j,k=fi1,j1,kdi+pi+di+pi

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e2+10;
const int maxm = 8e2+10;
const int base = 400;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, m;
int f[maxn][25][maxm]; 
int a[maxn], b[maxn];
int main(){
	
	int T = 1;
	vector<int> res;
	while(1){		
		res.clear();
		scanf("%d %d", &n, &m);
		if(n == m && n == 0)
			break;
		memset(f, -INF, sizeof(f));	
		for(int i = 1; i <= n; i++)
			scanf("%d %d", &a[i], &b[i]);
		//for(int i = 0; i <= m; i++)	
		f[0][0][base] = 0;
		for(int i = 1; i <= n; i++){
			for(int j = 0; j <= m; j++){
				for(int k = 0; k <= base * 2; k++){
					f[i][j][k] = f[i-1][j][k];
					if(j == 0)
						continue;
					int c = k - a[i] + b[i];
					if(c < 0 || c > 800)
						continue;
					f[i][j][k] = max(f[i][j][k], f[i-1][j-1][c] + a[i] + b[i]);				
				}
			}
		}
		
		int v = 0;
		while(f[n][m][base-v] < 0 && f[n][m][base+v] < 0)
			v++;
		if(f[n][m][base-v] > f[n][m][base+v])
			v = base-v;
		else
			v = base+v;
		
		int x = n, y = m;
		int sump = 0, sumd = 0;
		while(y){
			if(f[x][y][v] == f[x-1][y][v])
				x--;
			else{
				res.push_back(x);
				v -= (a[x]-b[x]);
				x--, y--;
			}
		}
		for(int i = 0; i < res.size(); i++){
			sump += a[res[i]];
			sumd += b[res[i]];
		}
		printf("Jury #%d\n", T++);
        printf("Best jury has value %d for prosecution and value %d for defence:\n", sump, sumd);
        sort(res.begin(), res.end());
		for(int i = 0; i < res.size(); i++){
            printf(" %d", res[i]);
        }
        putchar('\n');
        putchar('\n');
	}
	return 0;
}

硬币

题意:

给定 N N N 种硬币,其中第 i i i 种硬币的面值为 A i A_i Ai,共有 C i C_i Ci 个。

从中选出若干个硬币,把面值相加,若结果为 S S S,则称“面值 S S S 能被拼成”。

1 ∼ M 1∼M 1M 之间能被拼成的面值有多少个。

解析:

多重背包。

二进制拆分,将每种物品拆成 2 0 , 2 1 , . . . 2^0,2^1,... 20,21,... 个,然后01背包。

时间复杂度为 O ( n m l o g c ) O(nmlogc) O(nmlogc),没法通过此题。

正解应为单调队列优化。大致思路是:将体积按照对 A i A_i Ai 的余数分组,组之间互不影响。在同一组内部,维护一个价值递增的单调队列。用单调队列优化dp的转移。(因为比他set过了,就没写单调队列)

但对于此题,二进制拆分过不了,可以用bitset优化一下就过了。文章来源地址https://www.toymoban.com/news/detail-414865.html

代码:

#include<iostream>
#include<bitset>
using namespace std;

typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e2+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int a[maxn], c[maxn], w[maxm], tot;
int n, m;
bitset<maxm> f;

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

	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0)
			break;
		f.reset();
		tot = 0;
		for(int i = 1; i <= n; i++)
			cin >> a[i];
		for(int i = 1; i <= n; i++)
			cin >> c[i];
		for(int i = 1; i <= n; i++){
			int tmp = a[i];
			int cnt = 0, curw = 1;
			while(cnt + curw <= c[i]){
				w[++tot] = a[i];
				cnt += curw;
				
				curw <<= 1;
				a[i] <<= 1;				
			}
			c[i] -= cnt;
			if(c[i])
				w[++tot] = tmp * c[i];
		}
		
		f[0] = 1;
		for(int i = 1; i <= tot; i++){
			f = f | (f << w[i]);
		}
		int res = 0;
		for(int i = 1; i <= m; i++)
			res += f[i];
		cout << res << endl;
	}
	
	return 0;
}

到了这里,关于《算法竞赛进阶指南》0x52 背包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法竞赛必考算法——动态规划(01背包和完全背包)

    1.1题目介绍 1.2思路一介绍(二维数组) 代码如下: 1.3思路二介绍(一维数组) 空间优化   为什么可以使用一维数组?   我们先来看一看01背包问题的状态转移方程,我们可以发现 f[i]只用到了f[i-1],其他的是没有用到的,我们可以用滚动数组来做。   还有一个原因就是我

    2024年02月02日
    浏览(41)
  • 【程序设计竞赛算法】背包问题——贪心法

    贪心算法是一种基于贪心策略的算法,它在每一步选择中都采取当前状态下的最优选择,以期望最终达到全局最优解。 背包问题是一个经典的组合优化问题,可以分为 0-1 背包问题和分数背包问题。其中,0-1 背包问题要求物品只能选择一次,而分数背包问题允许物品被选择多

    2024年02月03日
    浏览(42)
  • 【图像分割】基于浣熊优化算法COA的Otsu(大津法)多阈值电表数字图像分割 电表数字识别【Matlab代码#52】

    长鼻浣熊优化算法(Cоati Optimization Algorithm,COA)是一种启发式优化算法,灵感来源于长鼻浣熊(Coati)的行为策略。长鼻浣熊优化算法基于长鼻浣熊在觅食过程中的特性和行为模式。长鼻浣熊是一种树栖动物,具有长而灵活的鼻子,用于觅食和捕食。它们通过嗅觉感知周围环

    2024年02月16日
    浏览(36)
  • 算法竞赛备赛进阶之数位DP训练

    数位DP的思想就是对每一位进行DP,计算时记忆化每一位可以有的状态,其作用是减少运算时间,避免重复计算。 数位DP是一种计数用的DP,一般就是要统计一个区间[A,B]内满足一些条件数的个数。 以1e9甚至1e18、1e100的问题为例,因为在统计情况下有很多重复的计算,数位DP实

    2024年01月16日
    浏览(48)
  • 算法题打卡day45-背包问题 | 70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数

    70. 爬楼梯 - 力扣(LeetCode) 状态:查看思路后AC。 除了常规的可以爬一或二级台阶,当题目稍微修改一下,变成可以爬m级台阶,之前的DP思路就有局限(dp[i] = dp[i-1] + dp[i-2),为了通杀这类问题,可以将题目转换为完全背包问题,可以爬的楼梯级数就是背包中的物品,楼梯总

    2024年02月11日
    浏览(46)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2281-2285)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月07日
    浏览(38)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2176-2200)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月09日
    浏览(40)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2051-2075)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2023年04月15日
    浏览(43)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2201-2225)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月08日
    浏览(32)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2271-2275)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月07日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包