10背包例题

末蓝、 2022-07-14 03:11 110阅读 0赞

**一个院级的acm小选拔赛，遇到的几个简单题目，这里做下总结**

**越野跑问题**

#include <iostream>
    using namespace std;
    int main()
    {
    	int M,T,U,F,D,sum=0;
    	cin>>M>>T>>U>>F>>D;
    	char *s=new char[T+1];
    	for(int i=0;i<T;i++)
    		cin>>s[i];
    	s[T]='\0';
    	int j;
        for(j=0;j<T;j++)
    	{
    		if(s[j]=='f') sum+=F*2;
    		else sum+=U+D;
    		if(sum>M) {cout<<j;break;}//j为数组下标，所以加一表所跑段数
    	}
    	if(j==T-1) cout<<j+1;
    	return 0;
    }

采药问题（这道题目是动态规划DP的经典例题01背包问题）

#include <iostream>
    //#include <algorithm>
    using namespace std;
    	const int Tmax=1000;
    	const int Mmax=100;
    	int T,M;//总时间数和总株数
        int *t=new int[M];
        int *w=new int[M];
    	int dp[Mmax][Tmax];	//化数组记忆，话说动态二维数组怎么建？
    
    int rec(int i,int j)
    {
    	if(dp[i][j]!=-1)  return dp[i][j];
    	int res;
    	if(i==M)  res=0;//被迷惑了好久，这里的判断条件是M
    	else if(t[i]>j) res=rec(i+1,j);
    	else res=max(rec(i+1,j),rec(i+1,j-t[i])+w[i]);
    	dp[i][j]=res;
    	return res;
    }
    int main()
    {
    	for(int i=0;i<Mmax;i++)
    	for(int j=0;j<Tmax;j++)
    			dp[i][j]=-1;
        cin>>T>>M;
        for(int i=0;i<M;i++)
        {
    		cin>>t[i]>>w[i];
        }
    
    	cout<<rec(0,T);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划算法经典例题_详解动态规划算法经典问题——零一背包

今天是周三算法与数据结构专题的第12篇文章，动态规划之零一背包问题。在之前的文章当中，我们一起探讨了二分、贪心、排序和搜索算法，今天我们来看另一个非常经典的算法——动态规划

落日映苍穹つ/ 2023年01月12日 11:34/ 0 赞/ 126 阅读

相关疯狂的采药（完全背包例题详解）

题目每种草药可以无限制地采摘，每种草药对应采药时间、草药价值，求在一定的采药时间下，采出的药最大总价值是多少。输入格式输入第一行有两个整数，分别代表总共能够用

「爱情、让人受尽委屈。」/ 2022年11月27日 05:23/ 0 赞/ 105 阅读

相关 Charm Bracelet（经典例题0-1背包）

https://ac.nowcoder.com/acm/problem/25029 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVp

Love The Way You Lie/ 2022年11月19日 04:27/ 0 赞/ 114 阅读

相关面试例题（1-10）

面向对象的基本概念面试例题1：面向对象技术的基本概念是什么？解析：按照定义，OO（面向对象）编程语言必须提供对象、类和继承。答案：对象、类和继承。面

た入场券/ 2022年10月05日 12:55/ 0 赞/ 121 阅读

相关 10 有依赖的背包问题（分组背包问题 + 树形dp）

1. 问题描述：有 N 个物品和一个容量是 V 的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。如下图所示： ![wat

比眉伴天荒/ 2022年08月28日 14:58/ 0 赞/ 139 阅读

相关 10背包例题

一个院级的acm小选拔赛，遇到的几个简单题目，这里做下总结越野跑问题 include <iostream> using namespace std;

末蓝、/ 2022年07月14日 03:11/ 0 赞/ 111 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 300 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 252 阅读

相关小白学习动态规划：完全背包（经典例题）

小白学习动态规划：完全背包参考博客： 1. https://blog.csdn.net/qq\_38984851/article/details/81133840

青旅半醒/ 2021年08月26日 18:23/ 0 赞/ 360 阅读

相关小白学习动态规划：0-1背包（经典例题）

前言背包问题只是动态规划问题下的一个分类，求解0-1背包问题的思路本质上与求解动态规划的一般思路是一致的，我们经常遇到新的题目做不出来，并不是因为没有掌握动态规划的思想

系统管理员/ 2021年05月12日 11:49/ 0 赞/ 438 阅读