采药题解

题解

A:

01背包的模板，直接往里套。

找准状态转移方程即可；

状态转移方程：

F[i,v]=max{F[i-1,v],F[i-1,v-c[i]]+w[i]}

后来，我将状态方程简化了，（就如同消除代数式中的同类项一样）

得到：F[v]=max{f[v],F[v-c[i]]+w[i]}

最后将F[v]输出

（注意F数组初始化为0，不要写-1,）

代码粘上

#include<stdio.h>
int max(int a,int b)
{
    if (a>b) return a;
    else return b;
    }
int main()
{
    int f[1000]={0},c[1000],w[1000];
    int n,v,i,j;
    scanf("%d%d",&v,&n);
    for(i=1;i<=n;i++)scanf("%d%d",&c[i],&w[i]);
    for(i=1;i<=n;i++)
    for(j=v;j>=c[i];j--)
    {
        f[j]=max(f[j],f[j-c[i]]+w[i]);
        }
    printf("%d ",f[v]);
    return 0;
    }

B:
动态规划->背包->01背包
01背包的特点:物品只有一件。想放就放，不想放就别放
思路(1 / 2):
1.定义二维数组 , f[i][j]表示采第i株药,花费时间j可以采到的草药的最大总价值。
2.输入采摘某株草药的时间和这株草药的价值。
3.判断是否采摘这株草药
1.不采摘(背包容量不够),则时间不变,当前采摘的药等于采摘的第i-1株药

f[i][j] = f[i - 1][j] ;

2.采摘(背包容量足够),那么当前可以获得的草药为采i-1株草药,时间为少采第i种药的时间j-ti[i]并且加上当前草药的价值pri[i]。

f[i][j] = f[i - 1][j - ti[i]] + pri[i] ;

这里需要注意 : 如果当前采摘这株草药获得的价值比采摘i-1株草药的价值低的话也不摘。
所以需要比较。因此无论摘不摘这一株草药,一开始的价值都应该是采摘i-1株草药的价值

f[i][j] = max(f[i][j], f[i - 1][j - ti[i]] + pri[i]) ;

相当于初始化当前可以获得的价值为采摘i-1株草药的价值，只有背包容量足够采摘当前这一株草药的时候,才判断是否采摘当前的这一株草药。

f[i][j] = f[i - 1][j] ;
    if(j >= ti[i]) 
        f[i][j] = max(f[i][j], f[i - 1][j - ti[i]] + pri[i]) ;

4.输出答案

#include<bits/stdc++.h>
using namespace std ;
int ti[1005] , pri[1005] ;
int f[1005][1005] ;
int main()
{
    int t , m ;
    cin >> t >> m ;
    for(int i = 1 ; i <= m ; ++i)
    {
        cin >> ti[i] >> pri[i] ;
        for(int j = 1 ; j <= t ; ++j)
        {
            f[i][j] = f[i - 1][j] ;
            if(j >= ti[i]) 
                f[i][j] = max(f[i][j], f[i - 1][j - ti[i]] + pri[i]) ;
        }
    }
    cout << f[m][t] ;
    return 0 ;
}

思路(2 / 2)
1.相比于第一种思路,最大的不同就是使用的是一维数组而不是二维数组,不记录i，只记录花费的时间j，其他的都与二维数组的思路没有什么太大的不同

#include<bits/stdc++.h>
using namespace std ;
int ti[1005] , pri[1005] ;
int f[1005] ;
int main()
{
    int t , m ;
    cin >> t >> m ;
    for(int i = 1 ; i <= m ; ++i)
        cin >> ti[i] >> pri[i] ;
    for(int i = 1 ; i <= m ; ++i)
        for(int j = t ; j >= 1 ; --j)
            if(j >= ti[i])
                f[j] = max(f[j] , f[j - ti[i]] + pri[i]) ;
    cout << f[t] ;
    return 0 ;
    }

C:

这道题的解法很多，大部分是动态规划和记忆化搜索，但是如果T一旦很大的话，动态规划和记忆化搜索会被卡掉。那我们有没有别的方法呢？是有的。

下面隆重介绍：

启发式搜索

启发式搜索是在暴力DFS基础上进行剪枝的搜索。你可能会说，不就是剪了一点枝吗，会快很多吗？答案是会。

我们先说一下，所有的启发式搜索都会有一个估价函数。下面是这一题的估价函数。

struct node
{
    int c,v;
    double cost;
};
const int N=10000;
node a[N+5];
inline int f(int t,int v)
{
    int tot=0;
    for(int i=1;t+i<=n;i++)
    {
        if(v>=a[t+i].c)
        {
            v-=a[t+i].c;
            tot+=a[t+i].v;
        }
        else return (int) (tot+v*a[t+i].cost);
    }
    return tot;
}

那么估价函数是什么呢？我们都知道，背包问题的最基础的思路是O(2^n)。一个状态有两种决策，分别是取和不取，那么，我们在取的时候判断一下是不是超过了体积，在不取的时候判断一下，如果，我不取这个，那么，剩下的所有的价值+现有的价值有没有大于我所找到的目前的最优解，如果没有，不取是没有意义的。听不懂？没关系。我们先上核心代码。

void DFS(int now,int cv,int cp)
{
    ans=code::max(ans,cp);
    if(now>n) {return;}
    if(f(now,cv)+cp>ans) DFS(now+1,cv,cp);
    if(cv-a[now].c>=0) DFS(now+1,cv-a[now].c,cp+a[now].v);
}

假设，我现在的最优解是2，如果我不取这个物品，所能得到的估价比这个小，说明不取是没有意义的，因为就算你剩下的全部取了都不是最优解。那么，估价有没有可能估小了呢？不可能。

    bool operator <(const node &a,const node &b)
    {
        return a.cost>b.cost;
    }
    sort(a+1,a+1+n);

上面这段代码就保证了不可能估小。以及，我们在估价时，不管它到底可不可以放进去，只有背包有空间，就放，而放的价值就是单位价值：

a[i].cost=1.0*a[i].v/a[i].c

好的，我们现在就放出完整代码。
代码均由本人实现

#include <algorithm>
#include <cctype>
#include <stdio.h>
int n, tot, ans;
struct node
{
    int c, v;
    double cost;
};
using namespace std;
const int N = 10000;
node a[N + 5];
int read() /*快读大法吼啊！*/
{
    int x = 0;short w = 0;char ch = 0;
    while (!isdigit(ch)){w |= ch == '-';ch = getchar();}
    while (isdigit(ch)){x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}
    return w ? -x : x;
}
inline int f(int t, int v) //估价函数，解释见上。
{
    int tot = 0;
    for (int i = 1; t + i <= n; i++)
    {
        if (v >= a[t + i].c)
        {
            v -= a[t + i].c;
            tot += a[t + i].v;
        }
        else
            return (int)(tot + v * a[t + i].cost);
    }
    return tot;
}
bool operator<(const node &a, const node &b)
{
    return a.cost > b.cost;
} /*等价于
bool cmp(node a,node b)
{
    return a.cost>b.cost;
}
*/
void DFS(int now, int cv, int cp)
{
    ans = max(ans, cp);
    if (now > n)
    {
        return;
    }
    if (f(now, cv) + cp > ans)
        DFS(now + 1, cv, cp);
    if (cv - a[now].c >= 0)
        DFS(now + 1, cv - a[now].c, cp + a[now].v);
}
int main()
{
    tot = read(), n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i].c = read(), a[i].v = read();
        a[i].cost = 1.0 * a[i].v / a[i].c;
    }
    sort(a + 1, a + 1 + n);
    DFS(0, tot, 0);
    printf("%d", ans);
    return 0;
}

D:

#include<iostream>
#include<cmath>//头文件
using namespace std;
int f[105][1005];//数组一定要多开几个，不然WA
int m,n,mi[105],vi[105];
int dfs(int x,int sumW)//把一个参数作为该函数的函数类型（优化一）
    {
    if(sumW>m)return -10000;//时间不能超出欧！
    if(f[x][sumW]) return/*（优化二）*/ f[x][sumW];//用一个数组来储存每一次dfs的数值，避免重复
    if(x==n+1) return 0;//到末尾了就返回0
    f[x][sumW]=max(dfs(x+1,sumW+mi[x])+vi[x],dfs(x+1,sumW));//取最大值，没啥好说的
    return f[x][sumW];//输出最大值
}
int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>mi[i]>>vi[i];
    }
    cout<<dfs(0,0)<<endl;
    return 0;
}