Knapsack

[LogicBaron]

Knapsack Problem List

Leetcode

1. 2291. Maximum Profit From Trading Stocks

[LogicBaron]

Knapsack 유형 1 : 한 번씩만 써서 목표값 달성하기

• 가능한 값들을 순회하면서,
• 만들 수 있는 값들에 대해서 큰 값 -> 작은 값으로 더한다.

예시 코드)

class Solution {
public:    
    int numberOfWays(int n, int x) {
        long long mod = 1e9+7;
        vector<long long> dp(n+1, 0);
        dp[0] = 1;

        for (int i = 1; pow(i, x)<=n; i++) {
            int ix = pow(i, x);
            for (int j = n; j>=ix; j--) {
                dp[j] = dp[j] + dp[j-ix];
                dp[j] %= mod;
            }
        }

        return dp[n];
    }
};