算法基础--动态规划（笔试记录）

蔚落 2022-05-08 05:52 174阅读 0赞

#include<iostream>
    using namespace std;
    
    int main()
    {
    	//输入部分 
    	//输入宝箱的个数n，和现在还剩余的魔法值w 
    	int n,w;
    	cin>>n>>w;
    	//int n = 5,w = 10;
    	int x,y;
    	//p[i]为第i个宝箱所需要的魔法值
    	//v[i]为第i个宝箱里面的金币数 
    	int p[n+1];
    	int v[n+1];
    	p[0] = 0;
    	v[0] = 0;
    	//输入第i个宝箱对应的金币数和所需魔法值 
    	for(int i = 1;i<=n;i++){
    	cin>>y>>x;
    	v[i] = y;
    	p[i] = x;
    	}
    	
    	int Preresult[w+1];
    	int t;
    	//先赋值 
    	for(int i = 1;i <= w;i++){
    		if(i<p[1])
    		{
    			Preresult[i] = 0;
    		 } 
    		else{
    			Preresult[i] = v[1];
    		}
    	}
    	
    	//使用动态规划的方法，使局部最优从而达到整体最优 
    	int result[w+1] = {0};
    	Preresult[0] = 0;
    	//n为宝箱的个数 
    	for(int i = 2;i<=n;i++){
    		//w为人数 
    		for(int j=1;j<=w;j++){
    			//总人数-一个宝箱需要的魔法值 
    			if(j<p[i]){
    				//赋予它一个相对来说特别小的数 
    				t = -123456;
    			}
    			else{
    				t = Preresult[j-p[i]];
    			}
    			result[j] = max(Preresult[j],t+v[i]);
    		}
    		for(int k = 1;k<=w;k++){
    			Preresult[k] = result[k];
    		}
    	} 
    	cout<<result[w]<<endl;
    	
     }

发表评论取消回复

表情：

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

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

相关阅读

相关算法-动态规划

在LeetCode上有一道题：[https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-tr

偏执的太偏执、/ 2022年12月28日 13:00/ 0 赞/ 242 阅读

相关【算法】动态规划

形成条件最优子问题重叠子问题 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a

爱被打了一巴掌/ 2022年12月01日 05:24/ 0 赞/ 196 阅读

相关动态规划算法

一：动态规划算法 1：动态规划算法介绍 1) 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获

╰半夏微凉°/ 2022年11月13日 05:28/ 0 赞/ 319 阅读

相关算法基础之动态规划

算法基础之动态规划（C++示例）动态规划（Dynamic Programming）指的是通过把一个问题递归拆解成更加简单的子问题的方式简化一个复杂问题。在计算机科学中，

迈不过友情╰/ 2022年09月07日 12:07/ 0 赞/ 226 阅读

相关动态规划算法

动态规划方法是对解最优问题的一种方法，一种途径，并不是一种特殊的算法。执行步骤： 1. 找出最优解的性质，刻画结

迈不过友情╰/ 2022年08月09日 02:14/ 0 赞/ 271 阅读

相关算法基础--动态规划（笔试记录）

include<iostream> using namespace std; int main() { //输入部分

蔚落/ 2022年05月08日 05:52/ 0 赞/ 175 阅读

相关动态规划算法

1.最长公共子串：转自：http://www.yuanma.org/data/2006/0723/article\_1215.htm 算法思想求字符串str1,st

ゝ一纸荒年。/ 2022年05月03日 15:58/ 0 赞/ 312 阅读

相关动态规划算法

1、最长公共子序列 > 定义网格：以s\[i\]和s\[j\]作为结尾的子字符串的最长子序列长度 > > 定义公式： > > s\[i\]\[j\] = s\[i

绝地灬酷狼/ 2022年03月15日 05:28/ 0 赞/ 319 阅读

相关算法——动态规划

文章目录 1.斐波那契数列 1.1递归法 1.2动态规划 1.3

怼烎@/ 2021年11月27日 02:52/ 0 赞/ 433 阅读

相关动态规划算法

一动态规划算法动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。动态规划算法与分治

╰+哭是因爲堅強的太久メ/ 2021年07月24日 22:41/ 0 赞/ 601 阅读