动态规划-01背包

先说一下什么是动态规划：
动态规划求解具有以下的性质：
　　最优子结构性质：子问题重叠性质　　
　　最优子结构性质：最优解包含了其子问题的最优解，不是合并所有子问题的解，而是找最优的一条解线路，选择部分子最优解来达到最终的最优解。
　　子问题重叠性质：先计算子问题的解，再由子问题的解去构造问题的解（由于子问题存在重叠，把子问题解记录下来为下一步使用，这样就直接可以从备忘录中读取）。其中备忘录中先记录初始状态。
　　
背包问题套路：
1、将原问题分解为子问题（子问题和原问题形式相同，且子问题解求出就会被保存）；
2、确定状态：01背包中一个状态就是个物体中第个是否放入体积为背包中；
3、确定一些初始状态（边界状态）的值；
4、确定状态转移方程，如何从一个或多个已知状态求出另一个未知状态的值。（递推型）

写题目时：
注意：dp的初始化条件；
01背包往往是这样子的：
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
往往问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
我们都可以知道，面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。

题目链接:
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
Sample Output
-45

32

 #include<stdio.h>
    #include< algorithm >
    #include<string.h>
    using namespace std;
    int main()
    {
   
        int t,m;
        int dp[1200];
        int a[1200];
        while(scanf("%d",&t)!=EOF)
        {
   
            memset(dp,0,sizeof(dp));//清零
            if(t==0)
                break;
            for(int i=0;i<t;i++)
            {
   
                scanf("%d",&a[i]);
            }
            scanf("%d",&m);
            sort(a,a+t);//排序一下找最大的菜价；//找出最大的进行排序；就可以更快找到最优解；
            if(m>=5)
            {
   
            for(int i=0;i<t-1;i++)//没必要找最后一个的最优解；
            {
   
                for(int j=m-5;j>=a[i];j--)
                {
   
                    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);//0 1选与不选中找它们的最大值；
                }
            }
             printf("%d\n",m-dp[m-5]-a[t-1]);//总的钱数-找出最优解的钱数-最后面的那个钱数；因为这里咱们没必要算最后一个的最优解，剩一个，所以就直接减去就可以了；
            }
            else
                printf("%d\n",m);
        }

题目链接

Problem Description
Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?

Input
There are several test cases in the input.
Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.
The input terminates by end of file marker.

Output
For each test case, output one integer, indicating maximum value iSea could get.

Sample Input
2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3

Sample Output
5
11
最近，伊莎去了一个古老的国家。在这么长的时间里，它是世界上最富有和最强大的王国。因此，即使他们的国家不再那么富有，这个国家的人民仍然非常自豪。
商人是最典型的，他们每个人只卖了一件商品，价格是π，但如果你的钱少于qi，他们会拒绝与你交易，并且isea评估每件商品的价值为vi。
如果他有M个货币单位，那么ISEA能得到的最大价值是多少？
输入
输入中有几个测试用例。 每个测试用例以两个整数n，m（1≤n≤500，1≤m≤5000）开始，表示项目编号和初始金额。 接下来是n行，每行包含三个数字pi、qi和vi（1≤pi≤qi≤100，1≤vi≤1000），其含义在描述中。 输入以文件结尾标记终止。
输出
对于每个测试用例，输出一个整数，表示ISEA可以得到的最大值。

//就是需要用结构体+sort排序；这样也是和上面的sort排序的道理差不多；
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define M 102010
int n,m,t,c,s;
using namespace std;
struct gg//本来是三个数据，多定义一个用来更好的排序；
{
   
    int x,y,z,u;
} mmp[M];
int cmp(gg a,gg b)
{
   
    return a.u<b.u;//排序，按高价格排好；
}
int main()
{
   
    while(scanf("%d%d",&n,&m)!=EOF)
    {
   
        int i;
        int dp[M];
        memset(dp,0,sizeof(dp));
        for(i=0; i<n; i++)
        {
   
            scanf("%d%d%d",&mmp[i].x,&mmp[i].y,&mmp[i].z);
            mmp[i].u=mmp[i].y-mmp[i].x;//这里是商人所定的要求，足够的资金减去它的价格得到的结果就可以判断出那个的价值更高；然后依次存放到结构体吗卖批[i].u里面；

        }
        sort(mmp,mmp+n,cmp);//排好价格；高的在最前面
        for(i=0;i<n;i++)
        {
   
            for(int j=m;j>=mmp[i].y;j--)//初始价格为自己的本金，每一次循环判断是否在最大利益下满足商人的要求；
            {
   
                dp[j]=max(dp[j],dp[j-mmp[i].x]+mmp[i].z);//dp，推出方程之前每个状态的最优解然后求当前状态的最优解；
            }
        }
        printf("%d\n",dp[m]);
    }
    return 0;
    }