[Usaco2008 Dec]Hay For Sale 购买干草

题目描述

约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草． 顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，

他最多可以运回多少体积的干草呢？

输入格式

第1行输入C和H，之后H行一行输入一个Vi．

输出格式

最多的可买干草体积．

很水的01背包裸题，敲着练手感。以免被人说成是大水怪，还是 象征性地 讲讲01背包的做法......

设dp(i,j)表示装到第i个物品，用去了j个单位体积时的最大价值；c[i]为第i个物品的重量，v[i]表示第i个物品的价值。那么显然：

\[ dp(i,j)= \left\{\begin{array}{rcl} max(dp(i-1,j-c[i])+v[i],dp(i-1,j)) & j>=c[i]\ dp(i-1,j) & j<c[i] \end{array}\right. \]

于是我们填一遍表就可以了，最终答案为dp(n,m).

可以发现对当前计算有用的只有第i层和第i-1层dp数组，之前的都已经没用了，所以可以用滚动数组优化一下：

\[ dp(d,j)= \left\{\begin{array}{rcl} max(dp(!d,j-c[i])+v[i],dp(!d,j))&j>=c[i]\ dp(!d,j)&j<c[i] \end{array}\right. \]

其实每次j下标的值都是由j-c[i]的值更新过来的，如果我们保证j下标比j-c[i]先更新，我们是可以用一维数组的。具体就是：把循环倒过来做。

\[ dp[j]=max(dp[j-c[i]]+v[i],dp[j]) \]

其时间复杂度为：

\[ O(NM) \]

空间复杂度为：

\[ O(m) \]

那么这题只需要求能够运回多少体积的干草，简直就是01背包的弱化版：

\[ dp[j]|=dp[j-c[i]] \]

初始化dp[0]=true，最后循环找一下最大的j，其dp[j]=true即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 5001
#define maxm 50001
using namespace std;
 
bool dp[maxm];
int n,m,c[maxn];
 
inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
 
int main(){
    m=read(),n=read();
    for(register int i=1;i<=n;i++) c[i]=read();
    dp[0]=true;
    for(register int i=1;i<=n;i++){
        for(register int j=m;j>=c[i];j--) if(dp[j-c[i]]){
            dp[j]=true;
        }
    }
    for(register int i=m;i>=0;i--) if(dp[i]){
        printf("%d\n",i); break;
    }
    return 0;
}

为什么我要给水题写这么长的题解

[Usaco2008 Dec]Hay For Sale 购买干草

原文：https://www.cnblogs.com/akura/p/10846620.html