【算法】背包DP

【题解】f[j]=(f[j-w[i]]+v[i]) 记得倒序(一个物品只能取一次)

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=10010;int n,W,w[maxn],v[maxn],f[maxn];int main(){    scanf("%d%d",&n,&W);    for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);    for(int i=1;i<=n;i++)    {        for(int j=W;j>=w[i];j--)        {            f[j]=max(f[j],f[j-w[i]]+v[i]);        }    }    printf("%d",f[W]);    return 0;}