solve the knapsack problem by dynamic planning

I'd like to solve the knapsack problem using dynamic planning, but somehow it's
Why?

I tried writing the code below to solve it as 1 origin, but it was not correct.
In many explanations, the transition of the dp table is

dp[i][p]—Maximum sum of values when the weight is selected not to exceed p from items up to i-1

It says
Is it possible to make it the maximum sum of the values when choosing items up to i (not i-1) so that the weight does not exceed p?

https://atcoder.jp/contests/dp/tasks/dp_d

Problem statement

There are N items. The items are numbered 1, 2, ..., N. For each i(1 ii NN), item i weighs wi
And the value is vi.

Taro chose some of the N items and decided to take them home in a backpack. The capacity of the backpack is W
The total weight of the items to be brought back must be less than or equal to W.

Find the maximum sum of the value of the items Taro brings back.

All constraint inputs are integers. 1 NN 1001001 WW 11051iwi 1W1ivi 109109

#include<bits/stdc++.h>

using lli = long long int;
template<typename T>
Boolean chmax(T&a,Tb){
    if(b>a){
        a = b;
        return true;
    }
    return false;
}

llin,w;
std::vector<std::pair<lli,lli>>vec;
std::vector<std::vector<li>>dp;


int main() {
    std::cin>>n>>w;
    vec.assign(n+1,{0,0});
    for(llii=0;i<n;i++){
        std::cin>>vec[i].first>vec[i].second;
    }
    dp.assign(n+1, std::vector<lli>(w+1,0));

    for(llii=1;i<=n;i++){
        for(lip=0;p<=w;p++){
            if(p>=vec[i].first){
                chmax(dp[i][p], dp[i-1][p-vec[i].first]+vec[i].second);
            }
            else{
                chmax(dp[i][p], dp[i-1][p]);
            }
        }
    }
    std::cout<<dp[n][w]<<std::endl;
}

c++ algorithm data-structure

2022-09-30 20:15

1 Answers

#include<bits/stdc++.h>

using lli = long long int;
template<typename T>
Boolean chmax(T&a,Tb){
    if(b>a){
        a = b;
        return true;
    }
    return false;
}

llin,w;
std::vector<std::pair<lli,lli>>vec;
std::vector<std::vector<li>>dp;


int main() {
    std::cin>>n>>w;
    vec.assign(n+1,{0,0});
    for(llii=0;i<n;i++){
        // std::cin>>vec[i].first>vec[i].second;
        std::cin>>vec[i+1].first>vec[i+1].second;
    }
    dp.assign(n+1, std::vector<lli>(w+1,0));

    for(llii=1;i<=n;i++){
        for(lip=0;p<=w;p++){
            if(p>=vec[i].first){
                chmax(dp[i][p], dp[i-1][p]);
                chmax(dp[i][p], dp[i-1][p-vec[i].first]+vec[i].second);
            }
            else{
                chmax(dp[i][p], dp[i-1][p]);
            }
        }
    }
    std::cout<<dp[n][w]<<std::endl;
}

I have confirmed that I will AC with this code.Perhaps the way the pairs were entered into the array was wrong.

2022-09-30 20:15

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656