洛谷 P2925 - Hay For Sale S

题目描述

P2925 [USACO08DEC]Hay For Sale S

解法：0-1背包问题

这里稍微有个优化：当马车早早被装满时，就可以结束程序输出结果了

#include <bits/stdc++.h>
using namespace std;int main()
{
    int c, h;cin >> c >> h;vector<int> v(h+1, 0);vector<int> dp(c+1, 0);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) break;}}cout << dp[c];return 0;
}