题解 | #【模板】01背包#

01背包模板思路

const auto io_sync_off=[]() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();


int w[1000];
int v[1000];
int dp[1000];
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=0;i<n;i++) {
        cin>>v[i]>>w[i];
    }
    // 0表示可以从任意状态转移到 j
    memset(dp,0,sizeof dp);
    for(int i=0;i<n;i++) {
        //由于每个物品只能用一次，为了防止重复计算，需要倒序遍历
        for(int j=V;j>=v[i];j--) {
            //状态转移，要么选择第i件物品，要么不选，取价值最大的
            dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
        }
    }
    int mx=dp[V];
    // 所有的状态都不可达，将0置为0， 即 所有的 j状态必须都要从0转移过去
    memset(dp,-0x3f,sizeof dp);
    dp[0] = 0;
    for(int i=0;i<n;i++) {
        for(int j=V;j>=v[i];j--) {
            dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
        }
    }
    printf("%d\n%d\n", max(mx,0), max(dp[V],0));
    
}