算法基础--动态规划（笔试记录）-蒲公英云

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

蔚落 2022-05-08 05:52 227阅读 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;
 }