首页 > 其他分享 >完全背包练习题

完全背包练习题

时间:2022-08-26 01:55:39浏览次数:100  
标签:练习题 输出 背包 return int 完全 include 256 dp


题目P2737

思路

这题准确的说,是『布尔型完全背包』。

先打一遍板子,很容易。

int n;
scanf("%d", &n);
dp[0] = true;
for (int i = 1; i <= n; i++)
{
	int a;
	scanf("%d", &a);
	for (int j = a; j <= ???; j++) dp[j] |= dp[j - a];
}

此处的 ??? 即上界,这个过一会详细说明。

这题最棘手的地方有两个。

第一个是输出的处理。

如果仅仅需要输出:顾客不能用包装盒买到麦香牛块的最大块数,那是非常容易的,使用这段代码即可:

for (int i = ???; i >= 0; i--)
	if (dp[i] == false)
	{
		printf("%d", i);
		return 0;
	}

但是!!!题目还要求:

如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限,输出 \(0\)。

我们再分两种情况解决。

  • 如果所有购买方案都能得到满足,输出 \(0\)。

    换句话说,全部 \(dp_i = true\)。

    所以,我们只需要在程序末尾输出 \(0\) 即可(因为满足的情况已经被 return 0 了)。

  • 如果顾客不能买到的块数没有上限,输出 \(0\)。

    稍微有点复杂。这里就是第二个棘手的地方。

    根据 『扩展欧几里德定理』,如果有不符合的数,必定会出现在 \(\max^{i=1}_{n}(a_i)^2\) 的范围里。

    说白了就是 \(256 \times 256 = 65536\) 的范围里。

    如果没有上限,说明范围内再加一个最大数也是不行的,即 \(65536\) 至 \(256 \times 257 = 65792\) 有数不符合。

那么代码就很简单了。

整体评价

本题实现并不困难,在思路上有些难度。

绿题非常合理。

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define M 65536   //256*256
#define MM 65792  //256*257
using namespace std;
int dp[MM + 5];
int main()
{
	int n;
	scanf("%d", &n);
	dp[0] = true;
	for (int i = 1; i <= n; i++)
	{
		int a;
		scanf("%d", &a);
		for (int j = a; j <= MM; j++) dp[j] |= dp[j - a];
	}
	
	for (int i = M; i <= MM; i++)
		if (dp[i] == false)
		{
			printf("0");
			return 0;
		}
	
	for (int i = M-1; i >= 0; i--)
		if (dp[i] == false)
		{
			printf("%d", i);
			return 0;
		}
	printf("0");
	return 0;
}

首发:2022-04-25 17:08:15

标签:练习题,输出,背包,return,int,完全,include,256,dp
From: https://www.cnblogs.com/liangbowen/p/16622857.html

相关文章

  • Mysql入门练习题
    1、在students表中,查询年龄大于25岁,且为男性的同学的名字和年龄mysql>selectname,agefromstudentswhereage>25andgender='M';+---------------+-----+|name......
  • leetcode222-完全二叉树的节点个数
    完全二叉树的节点个数递归classSolution{publicintcountNodes(TreeNoderoot){if(root==null)return0;returncountNodes(root.le......
  • 背包学习笔记
    ##前言最近学习了背包,来写篇学习笔记。如果你想认真看这篇笔记,可以参考配套题单,这些题目在下文练习题中也会提到。目录什么是背包01背包无优化空间优化......
  • Java基础练习题-错题集(三)
    (1)我们在程序中经常使用“System.out.println()”来输出信息,语句中的System是包名,out是类名,println是方法名。选项:A. 对B.错 (2)以下哪些继承自 Collection 接口()选......
  • 手机类练习题
    手机类练习题案例:DemoPhone1类://成员变量Stringbrand;//品牌intprice;//价格Stringcolor;//颜色//成员方法publicvoidcall(Stringwho){System.out.println("......
  • 背包问题
    前言本文将基于各大优质博客题解并加之个人的总结,主要内容包括四类背包问题:0-1背包问题,完全背包问题,多重背包问题和分组背包问题。0-1背包问题题目题解代码1.二维版......
  • NOIP模拟赛 背包
    NOIP模拟赛背包题面NYG有一个神奇的背包,每放进去一个物品,背包的体积就会变大。也就是说,每放进一个物品,背包会被占用一定的体积,但是紧接着背包的总体积又会增大一定的值......
  • Java基础练习题目
    2.基础练习2.1减肥计划if版本【应用】2.1.1案例需求​ 输入星期数,显示今天的减肥活动​周一:跑步​周二:游泳​周三:慢走​......
  • Redis基础练习题-错题集(一)
    (1)下面关于Redis中set数据类型与list数据类型的比较,正确的说法是()选项A. set中的数据具有唯一性,list中的数据不具有唯一性B. set中的数据有序,list中的数据无序......
  • LeetCode 367. 有效的完全平方数
    LeetCode367.有效的完全平方数思路:核心为最后一步判断当二分结束后值为及接近一个整数的浮点数(如2.9xxxx)此时加上极小数(1e-6)取整再平方,若与num相等则为完全平方数......