【关于一个单身狗在七夕向大家分享的简单必会算法题】
七夕来袭!是时候展现专属于程序员的浪漫了!单身狗的我选择了刷题hhh
直接上题吧
多重背包问题 I
有 NN 种物品和一个容量是 VV 的背包。
第 ii 种物品最多有 sisi 件,每件体积是 vivi,价值是 wiwi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,VN,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 NN 行,每行三个整数 vi,wi,sivi,wi,si,用空格隔开,分别表示第 ii 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000<N,V≤100
0<vi,wi,si≤1000<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
其实代码没什么特别多说的,这些都是板子题,还是需要大家多练。
AC:
#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 110 ;
int n, m ;
int v[N], w[N] ,s[N] ;
int f[N][N] ;
int main()
{
cin >> n >> m ;
for(int i=1; i<=n; i++)
{
cin >> v[i] >> w[i] >> s[i] ;
}
for(int i=1; i<=n; i++)
{
for(int j=0; j<=m; j++)
{
for(int k=0; k<=s[i] && k*v[i]<=j; k++)
{
f[i][j] = max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k) ;
}
}
}
for(int i=1; i<=n; i++)
{
for(int j=0; i<=m; j++)
{
for(int k=0; k<=s[i] && k*v[i]<=j; k++)
{
f[i][j] = max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k) ;
}
}
}
cout << f[n][m] << endl ;
return 0 ;
}
多重背包问题 II
有 NN 种物品和一个容量是 VV 的背包。
第 ii 种物品最多有 sisi 件,每件体积是 vivi,价值是 wiwi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,VN,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 NN 行,每行三个整数 vi,wi,sivi,wi,si,用空格隔开,分别表示第 ii 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N≤10000<N≤1000
0<V≤20000<V≤2000
0<vi,wi,si≤20000<vi,wi,si≤2000
提示:
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
AC:
#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 12010, M = 2010 ;
int n , m;
int v[N], w[N] ;
int f[M] ;
int main()
{
cin >> n >> m ;
int cnt = 0 ;
for(int i=1; i<=n; i++)
{
int a, b ,s ;
cin >> a >> b >> s ;
int k = 1 ;
while(s>=k)
{
cnt++ ;
v[cnt] = a*k ;
w[cnt] = b*k ;
s-=k ;
k*=2 ;
}
if(s>=0)
{
cnt++ ;
v[cnt] = a*s ;
w[cnt] = b*s ;
}
}
n = cnt ;
for(int i=1; i<=n; i++)
{
for(int j=m; j>=v[i]; j--)
{
f[j] = max(f[j], f[j-v[i]]+w[i]) ;
}
}
cout << f[m] << endl ;
return 0 ;
}
好了,今天就向大家分享这两个简单的板子题,当然背包问题还有更多板子,如果大家需要详细解答的话,可以在文章下面给我留言,这样我会将这两个题以及之后的推荐算法题都向大家做一个讲解的。
当然最后也是祝大家七夕节快乐,每天开心,开心学编程。我们一起加油
相关文章
- 学算法必备的一个网站与 app
- c#打包文件解压缩 C#中使用委托、接口、匿名方法、泛型委托实现加减乘除算法 一个简单例子理解C#的协变和逆变 对于过长字符串的大小比对
- 一个简单的QQ隐藏图生成算法 通过jQuery和C#分别实现对.NET Core Web Api的访问以及文件上传
- 算法 - 求一个数组的最长递减子序列(C++)
- 【算法】【字符串模块】判断字符串是否都只出现过一次
- 【算法】【栈和队列模块】只用一个栈来排序另一个栈
- 【算法】【栈和队列模块】使用递归方式逆序一个栈
- 【算法】【栈和队列模块】使用栈数据结构实现一个队列的基本功能
- 【算法】【栈和队列模块】求一个[0,1]矩阵中最大的1矩阵面积
- 骑摩托的蒙娜丽莎 - 曼妙风骚的花式慢跑算法
- KMP算法预备知识:字符串match的每一个位置i之前的字符串,前缀与后缀匹配的最大长度是多少
- C#,普洛尼克数(Pronic Number)的算法与源代码
- 页缓存算法(页面置换算法)
- 一个按权重(weight)进行LB的算法
- 又是一个渐变色生成算法
- 算法设计是分多层,每一个是一个抽象,最上面一层是最抽象的,越往下抽象的概念越少功能越具体
- 动手实现 LRU 算法,以及 Caffeine 和 Redis 中的缓存淘汰策略
- 随机采样一致性算法RANSAC
- 122、【回溯算法】leetcode ——90. 子集 II:子集去重(C++版本)
- 整型数组处理算法(十二)请实现一个函数:最长顺子。[风林火山]
- acwing算法基础课学习笔记(第一章:基础算法)
- 华为OD机试 - 考勤信息(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 【源代码】将一个整数的每位数分解并按逆序放入一个数组中(用递归算法)(C语言实现)
- 冒泡算法应用(坐标Y值降序X值升序)
- 堆算法(二叉树创建、遍历)