Elearning CodePath – CTP Online Judge

🎯 Mục tiêu bài học

Hiểu cách sử dụng DP 2 chiều để chọn vật phẩm tối ưu.
Nắm được công thức chuyển trạng thái của bài toán Balo.

📘 Mô tả bài toán

Có n vật, vật i có trọng lượng w[i] và giá trị v[i]. Balo chịu tải tối đa W. Tìm tổng giá trị lớn nhất có thể mang được mà không vượt quá W.

📐 Công thức DP

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) nếu j ≥ w[i]

💻 Thực hành

C++

#include 
using namespace std;
int main(){
    int n,W;cin>>n>>W;
    vector w(n+1),v(n+1);
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    vector> dp(n+1,vector(W+1,0));
    for(int i=1;i<=n;i++)
        for(int j=0;j<=W;j++)
            dp[i][j]= (j



Python
n,W=map(int,input().split())
w,v=[0],[0]
for _ in range(n):
    wi,vi=map(int,input().split())
    w.append(wi);v.append(vi)
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(W+1):
        if j




🧩 Bài tập luyện tập

  Thử thay đổi dữ liệu đầu vào và quan sát cách DP thay đổi.
  In ra danh sách các vật được chọn.
  Tối ưu bộ nhớ bằng cách dùng mảng 1 chiều dp[j].



  💡 Xem lời giải mẫu
  # Python (1D DP)
n,W=map(int,input().split())
w,v=[],[]
for _ in range(n):
    wi,vi=map(int,input().split())
    w.append(wi);v.append(vi)
dp=[0]*(W+1)
for i in range(n):
    for j in range(W,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
print(dp[W])