炎帝出题让精卫填大海😄 ： 思路： (1)状态定义: 定义f表示消耗i的体力最多可以搬运的体积(2)初始状态: 不需要特殊处理，嗯其实是因为消耗0体力能搬运的体积维0。(3)状态转移: 就是一个简单的01背包问题，就不多做解释fj]= max(fj],fj- tl{i]]+ tj[i]);(4)结果输出: 最后我们就可以判断用全部的体力(也就是i== c)是否能填平，如果不能，就输出"Impossibel"，不然就一直向下找，直到找到刚好够填平时消耗的体力，用总体力一减，就是答案了 思路抄：

#include <bits/stdc++.h>
using namespace std;
int v,n,c,ans=INT_MAX;
struct R
{
    int k,m;
}q[10005];
int sum=0;
int f[10000000];
int main()
{
   cin>>v>>n>>c;
   for(int i=1;i<=n;i++)
   {
      cin>>q[i].k>>q[i].m;
      sum=max(q[i].k,sum);
   }
   sum+=v;
   for(int j=1;j<=sum;j++)
      f[j]=1e7; 
   f[0]=0;
   for(int i=1;i<=n;i++)
   {
      for(int j=sum;j>=q[i].k;j--)
      {
         f[j]=min(f[j],f[j-q[i].k]+q[i].m);
      }
   }
   for(int j=v;j<=sum;j++)
   {
      ans=min(f[j],ans);
   }
   if(ans>c)
      cout << "Impossible";
   else 
      cout<<c-ans;
    return 0;
}

思路点拨

（搬过来的石头的体积和 以下简称总体积）

1.总体积可以大于v。

2.总体积不超过（v+max(k））大于这个值均不是最优方案。

#include<bits/stdc++.h>
using namespace std;
int v,n,c,ans=INT_MAX;
struct R
{
    int k,m;
}q[10005];
int sum=0;
int f[10000000];



int main()
{
    cin>>v>>n>>c;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i].k>>q[i].m;
        sum=max(q[i].k,sum);
    }
    sum+=v;
    for(int j=1;j<=sum;j++)f[j]=1e7;
    
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=sum;j>=q[i].k;j--)
        {
            f[j]=min(f[j],f[j-q[i].k]+q[i].m);
        }
    }
    for(int j=v;j<=sum;j++)
    {
        ans=min(f[j],ans);
    }
    if(ans>c)cout<<"Impossible";
    else cout<<c-ans;
    return 0;
}

#include<iostream>
using namespace std;
int v, n, c, tj[10002], tl[10002];
int f[10002];
int main()
{
    cin >> v >> n >> c;
    for (int i = 1; i <= n; i++)
        cin >> tj[i] >> tl[i];
    for (int i = 1; i <= n; i++)
        for (int j = c; j >= tl[i]; j--)
            f[j] = max(f[j], f[j - tl[i]] + tj[i]);
    if (f[c] < v)
        cout << "Impossible";
    else
    {
        int i = c;
        while (f[i] >= v) i--;
        cout << c - (i + 1);
    }
    return 0;
}