DP动态规划的01背包问题---洛谷---开心的金明

ゝ一纸荒年。 2023-06-28 06:27 18阅读 0赞

## 一.记录下（自己的感受） ##

今天刚学会01背包问题，之前一直搁着没学，看的一知半懂，今天认真看了下，总算学会了，可能是军训脑袋放空后学的容易点吧！！  
说到01背包，一般的方法都是DFS或者动态规划。不过动态规划的01背包貌似有个缺点，就是数据量一大的话，耗时很大，做一些题目的时候很容易超时。  
今年晚上就拿了洛谷的一道题，试试水，看看自己掌握的咋样。

## 二.开心的金明 ##

[点击进入题目][Link 1]  
题目描述  
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1−5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。  
请你帮助金明设计一个满足要求的购物单。

输入格式  
第一行，为2个正整数，用一个空格隔开：n m（其中N(<30000)表示总钱数，m(<25)为希望购买物品的个数。）

从第2行到第m+1行，第jj行给出了编号为j−1的物品的基本数据，每行有2个非负整数 v p（其中v表示该物品的价格(v≤10000)，p表示该物品的重要度(1−5)

输出格式  
1个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。

输入输出样例  
输入 \#1 复制  
1000 5  
800 2  
400 5  
300 5  
400 3  
200 2  
输出 \#1 复制  
3900  
说明/提示  
NOIP 2006 普及组 第二题

这题是明显的01背包问题，具体的01背包是啥我就不说了，去百度有更加专业的解答。  
对于01背包问题，每一个现在的情况的前面一个情况对应的都是最优情况，所以01背包问题的每一个情况对应的都是最优的情况，所以都是最优子结构。  
众所周知01背包问题有个公式，这题就是把这个公式直接套用即可，下面给出这个公式dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i-1\]\[j-w\[i\]\]+v\[i\]);  
先说明一下，我的这个公式中dp数组对应的是动态规划表，w的数组对应的是物品的重量，v对应的是物品的价值。这题因为要求的是物品的价值和价钱的乘积最大，所以只需要将v【i】改成对应的物品的价值和价钱的乘积即可。  
至于这个公式怎么理解，前面说过，每一种情况都是最优子结构，所以对于目前这个情况，要么选这个物品，要么不选，取这两个的最大值即可。

#include<iostream>
    #include<cstdlib>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define ll long long
    int hope[30][2];
    int n,m;//n为money,m is hope
    int mp[30][30008];
    void defmap()//制作动态规划表
    {
        
        for(int i=1;i<=m;i++)
        {
        
            for(int j=1;j<=n;j++)
            {
        
                if(j<hope[i][0])  mp[i][j]=mp[i-1][j];
                else
                {
        
                    mp[i][j]=max(mp[i-1][j],mp[i-1][j-hope[i][0]]+hope[i][0]*hope[i][1]);
    
                }
            }
        }
    }
    int main()
    {
        
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>hope[i][0]>>hope[i][1];//输入想购买的物品的信息;0是价格，1是重要度
    for(int i=0;i<m;i++)//排序
    {
        
        for(int j=1;j<m-i;j++)
        {
        
            if(hope[j][0]>hope[j+1][0])
            {
        
                int temp;
                temp=hope[j][0];
                hope[j][0]=hope[j+1][0];
                hope[j+1][0]=temp;
                temp=hope[j][1];
                hope[j][1]=hope[j+1][1];
                hope[j+1][1]=temp;
            }
        }
    }
    defmap();
    cout<<mp[m][n];
        return 0;
    }

说明一下，这个代码可以优化，直接把我的那个排序换成sort就行，不过要自己定义一个比较函数。这样的话运行速度会更加快些。

[Link 1]: https://www.luogu.com.cn/problem/P1060