题解 P1048 【采药】

x_forever · 2018-03-26 20:54:33 · 题解

这道题没有什么特殊之处，直接把0/1 背包的代码复制上去就可以了！！！！！！！！

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
short v[101],w[101],m[101][1001];
short n,c;
cin>>c>>n;
for (short i=1;i<=n;i++) cin>>w[i]>>v[i];
memset(m,0,sizeof(m));
for(short i=1;i<=n;i++){
    for(short j=1;j<=c;j++){
        if(j>=w[i]) m[i][j]=max(m[i-1][j],short(m[i-1][j-w[i]]+v[i]));
            else m[i][j]=m[i-1][j];}}
cout<<m[n][c];
return 0;
}