Viết chương trình C. Nhập n phần quà từ bàn phím và giá trị từng phần quà. Mỗi lượt chỉ được chọn 1 món quà. Nếu lượt này đã chọn món quà thứ k thì lượt sau chỉ được chọn các phần quà từ k+1 đến n-1 . Ở lượt chọn quà lẻ thì Hải được chọn bất kỳ phần quà giá trị tùy ý. Ở lượt chọn quà chẵn thì Hải bắt buộc phải chọn phần quà có cùng giá trị với phần quà ngay trước đó mà Hải đã chọn. Hãy tìm và in ra tổng giá trị lớn nhất của các phần quà mà Hải có thể chọn. Ví dụ: Nhập số lượng phần quà: 5 Nhập giá trị của phần quà thứ 1: 10 Nhập giá trị của phần quà thứ 2: 6 Nhập giá trị của phần quà thứ 3: 7 Nhập giá trị của phần quà thứ 4: 6 Nhập giá trị của phần quà thứ 5: 1 Tổng giá trị lớn nhất của các phần quà mà Hải có thể chọn là: 13 . Giải thích: Lượt 1 Hải chọn phần quà có giá trị a[1]=6 Lượt 2 Hải chọn phần quà có giá trị a[3] =6 Lượt 3 Hải chọn phần quà có giá trị a[4] =1
Dưới đây là một bản minh họa cho chương trình C bạn đang muốn viết.
#include<stdio.h>
int main() {
int n, i;
printf("Nhập số lượng phần quà: ");
scanf("%d", &n);
int arr[n];
for (i = 0; i < n; i++) {
printf("Nhập giá trị của phần quà thứ %d: ", i+1);
scanf("%d", &arr[i]);
}
int dp[n];
for (i = 0; i < n; i++)
dp[i] = 0;
dp[0] = arr[0];
for (i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] == arr[i] || j == i-1) {
dp[i] = dp[i] > dp[j] + arr[i] ? dp[i] : dp[j] + arr[i];
} else {
dp[i] = dp[i] > dp[j] ? dp[i] : dp[j];
}
}
}
int max = dp[0];
for (i = 1; i < n; i++)
if (max < dp[i])
max = dp[i];
printf("Tổng giá trị lớn nhất của các phần quà mà Hải có thể chọn là: %d\n", max);
return 0;
}Chương trình này sử dụng phương pháp quy hoạch động để xác định giá trị tối đa mà Hải có thể giành được từ các món quà.
Rất vui nếu bạn có thể ghé thăm trituenhantao.io - nơi bạn có thể cập nhật các thông tin mới nhất về AI, công nghệ và các chủ đề liên quan. Đừng quên mang theo một tách cà phê, bởi vì riêng với lập trình, chúng ta luôn sẵn lòng thức đêm!