제출 #1277776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277776		huy_init	Knapsack (NOI18_knapsack)	C++17	37 / 100	2 ms	580 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
/* 
 _  ____  ____  ____ 
/ \/   _\/  __\/   _\
| ||  /  |  \/||  /  
| ||  \__|  __/|  \__
\_/\____/\_/   \____/
*/
#define mask(x) (1 << x)
#define all(x) x.begin(), x.end()
#define int long long
/* FUNCTIONS */

void ckmax(int &a, int b) { a = max(a, b); }
void ckmin(int &a, int b) { a = min(a, b); }
int gcd(int a, int b) { if (b==0) return a; return gcd(b, a%b); }
int lcm(int a, int b) { return a/gcd(a,b)*b; }
struct item{int v, w, k;};
signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    while (t--) 
    {
        // code here
        int s, n; cin >> s >> n;
        vector<item> a(n);
        int sum = 0;
        for (int i=0; i<n; i++) 
        {
            cin >> a[i].v >> a[i].w >> a[i].k;
            sum += a[i].w;
        }
        if (n == 1) 
        {
            cout << min(a[0].k, s / a[0].w) << endl;
        }
        else 
        {
            vector<int> dp(s + 1, 0); // giá trị lớn nhất với trọng lượng là i sao cho tổng <= s 
            int ans = 0;
            for (int i=0; i<n; i++) 
            {
                for (int j=1; j<=a[i].k; j+=1)
                {
                    for (int W=s; W>=a[i].w; W-=1) 
                    {
                        ckmax(dp[W], dp[W - a[i].w] + a[i].v);
                    }
                }
            }
            for (int i=0; i<=s; i++) 
            {   
                ckmax(ans, dp[i]);
            }
            cout << ans << endl;
        }
    }
    return 0; 
}

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27