THUHOACH - Thu hoạch vụ mùa
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
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; }
test 5 6 là gì v ạ
Ý 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ở.
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]; }
ủa bài quy hoạch động mà mình cài quay lui cũng ac này =))
import java.util.Scanner;
public class THUHOACH { public static void main(String[] args) { Scanner sc = new Scanner(System.in);
}
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;
}
ai cho mình xin í tưởng đc ko bí quá :v
dùng quy hoạch động nha
test case 5 là gì vậy ạ
test case so 5 la sao v sao tui sai
ok