[USACO08DEC]Hay For Sale

Hay For Sale

洛谷题目链接Hay For Sale

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

解题思路
典型的01背包问题，每包干草只有拿或不拿两种情况，每件物品的价值和重量相同，直接套板子就行

• 板子

for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
        }
    }

但是用普通的01背包并不能通过,我在每次装完一包干草后都加了一个判断,如果已经装满就直接退出,不加判断则会超时

附上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f;
int v[5010];
int dp[50010];
int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);cout.tie(0);
 
 int c,h;
 cin>>c>>h;
 for(int i=1;i<=h;i++)
  cin>>v[i];
 for(int i=1;i<=h;i++){
  for(int j=c;j>=v[i];j--){
   dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
  }
  if(dp[c]==c){
   cout<<c<<endl;
   return 0;
  }
 }
 cout<<dp[c]<<endl;
 return 0;
}