THUHOACH - Thu hoạch vụ mùa

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Hiện đang vào mùa thu hoạch ngô, nhà Tí có một chiếc công nông tải trọng có hạn, chỉ chở được tối đa ~C~ (kg), trong khi đó nhà Tí lại thu được ~N~ bao ngô, bao thứ ~i~ có khối lượng là ~w_i~ (kg), hãy giúp Tí tính xem một chuyến xe nhà Tí có thể chở được khối lượng ngô tối đa là bao nhiêu?

Input

  • Dòng đầu chứa hai số nguyên dương ~N,C~;
  • Dòng thứ hai chứa ~N~ số nguyên dương ~w_1, w_2, …, w_N~, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

  • ~1 ≤ N ≤ 20, 1 ≤ C, w_i ≤ 50000~.

Output

  • Một số nguyên duy nhất là khối lượng ngô tối đa xe nhà tí chở được trong một chuyến.

Sample

Input #1
5 259
81 58 42 33 61
Output #1
242

Hint

Giải thích #1:

  • Chở các bao ngô số ~1, 2, 3, 5~ ta có tổng khối lượng là: ~81+58+42+61 = 242~, đây là tổng khối lượng ngô lớn nhất có thể chở được.

Problem source: Chuyên Sơn La Online Judge


Comments

Please read the guidelines before commenting.



  • 0
    hoangvinhkhanh  commented on May 19, 2024, 8:52 a.m.

    Bài này ta nên làm thuật toán quy hoạch động:

    n, c = map(int, input().split()) weight = list(map(int, (input().strip()).split())) dp = [0] * (c + 1) for w in weight: for i in range(c, w - 1, -1): dp[i] = max(dp[i], dp[i - w] + w) print(dp[c])


  • 0
    vanminhk27  commented on May 19, 2024, 8:49 a.m.

    bài này chúng ta sử dụng thuật toán balo trong quy hoạch động: a=input().split(" ") n=int(a[0]) c=int(a[1]) b=input() weights=list(map(int,b.strip().split(" ")))# danh sách đã chuyển sang kiểu int dp=[0]*(c+1) for w in weights: for i in range(c,w-1,-1): dp[i]=max(dp[i],dp[i-w]+w)

    print(dp)

    print(dp[c])


  • 0
    osaku115  commented on April 27, 2024, 12:29 p.m.

    include <bits/stdc++.h>

    define ll long long

    using namespace std;

    int main() { ll n,m; cin>>n>>m; vector<ll>a(n+1); for(ll i=0;i<n;i++){ cin>>a[i]; } vector<ll>dp(m+1,0); for(ll i=0;i<n;i++){ for(ll j=m;j>=a[i];j--){ dp[j]=max(dp[j],dp[j-a[i]]+a[i]); } } cout<<*max_element(dp.begin(),dp.end()); return 0; }


  • 0
    kieuly123  commented on April 20, 2024, 8:21 a.m.

    test 5 6 là gì v ạ


  • 1
    bnshuyenthoainvta  commented on March 23, 2024, 3:58 a.m.

    Ý tưởng là dùng quay lui tìm tất cả tổng max của số bao ngô có thể chọn từ 0 đến n; sau đó lấy một mảng khác hứng kết quả các tổng max đó; sau đó so sánh kết quả trong tổng max đó với trọng tải của xe để ra được số kg ngô lớn nhất có thể chở.


  • 0
    bnshuyenthoainvta  commented on March 23, 2024, 3:56 a.m.

    include<iostream>

    using namespace std; int n,C; int arr[10]; int chua[10]; int gtln=0; int S=0; int sosanh[10];

    void ketqua(){ for(int i=0;i<n;i++) S=S+chua[i]; gtln=max(gtln,S); }

    void quaylui(int k,int j,int x){ if(k>x) {ketqua(); S=0;} else for(int i=j;i<n;i++) { chua[k]= arr[i]; quaylui(k+1,i+1,x);} }

    int main(){ cin>>n>>C; int dem=0; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=0;i<n;i++){quaylui(0,0,i); sosanh[i]=gtln;} for(int i=0;i<n;i++){if(sosanh[i]<=C) dem++;} if(sosanh[dem-1]==C) cout<< C; else cout<< sosanh[dem-1]; }


  • 0
    NguyenBuiVN  commented on March 3, 2024, 11:55 a.m.

    ủa bài quy hoạch động mà mình cài quay lui cũng ac này =))


    • 0
      lehongduc  commented on May 15, 2024, 2:28 p.m.

      do N<=20 ak chứ mà N<=10^6 là xong đáy:)


  • 3
    ngochahh2005  commented on Feb. 8, 2024, 10:01 a.m.

    import java.util.Scanner;

    public class THUHOACH { public static void main(String[] args) { Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), c = sc.nextInt();
        int[] w = new int[n+3];
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        int[][] dp = new int[n+3][c+3];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c; j++) {
                dp[i][j] = dp[i-1][j];
                if (w[i] <= j) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w[i]] + w[i]);
            }
        }
        System.out.println(dp[n][c]);
    
        sc.close();
    }
    

    }


  • 0
    ChauCao  commented on Dec. 12, 2023, 5:05 a.m.

    include <iostream>

    include <vector>

    using namespace std; int main() { int n, c; cin >> n >> c; vector w(n + 1, vector<int>(c + 1)); for (int i = 1; i <= n; ++i) cin >> w[i][0]; vector dp(n + 1, vector<int>(c + 1)); for (int i = 1; i <= n; ++i) { for (int j = 0; j <= c; ++j) { dp[i][j] = dp[i - 1][j]; if (j >= w[i][0]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i][0]] + w[i][0]); } } } cout << dp[n][c] << endl; return 0; }


  • 4
    TQThong2k11  commented on Dec. 7, 2023, 4:13 a.m.

    ai cho mình xin í tưởng đc ko bí quá :v


    • 1
      quanvannam252  commented on Feb. 22, 2024, 9:50 a.m.

      dùng quy hoạch động nha


  • 1
    leminhtripython  commented on Nov. 3, 2023, 2:36 p.m.

    test case 5 là gì vậy ạ


  • -2
    huhu_tuingucode  commented on Sept. 14, 2023, 10:34 a.m.

    test case so 5 la sao v sao tui sai


  • 0
    Vuthienhan6209  commented on Sept. 14, 2023, 8:53 a.m.

    ok