Bài toán cái túi: 0/1, không giới hạn và chiều vòng lặp

Đọc đề để biết món nào được dùng lại

Bạn có sức chứa W, mỗi món có khối lượng w và giá trị v. Muốn chọn một số món sao cho tổng khối lượng không vượt W, tổng giá trị lớn nhất. Hai đề nhìn rất giống nhau nhưng có thể khác luật: mỗi món chỉ có một bản, hoặc mỗi loại có vô hạn bản để lấy.

Xét sức chứa 7 và ba loại (khối lượng,giá trị) là (3,4), (4,5), (2,3). Trong bản 0/1, lấy món 3 và món 4 cho tổng giá trị 9. Trong bản không giới hạn, có thể lấy khối lượng 3,2,2 cho giá trị 4+3+3=10. Nếu không chốt luật số lượng, rất dễ viết đúng công thức cho một bài khác.

Không có quy tắc tham lam chung theo giá trị lớn nhất, nhẹ nhất hay tỉ lệ v/w cho bản nguyên 0/1. Bài được phép chia nhỏ vật phẩm có tính chất khác và thường dùng tham lam theo tỉ lệ. Đừng lấy lời giải của cái túi chia nhỏ áp cho bài chọn nguyên món.

Xây bảng hai chiều trước

Đặt D[i][c] là tổng giá trị lớn nhất khi chỉ xét i món đầu và dùng khối lượng không quá c. Nếu không lấy món thứ i, kết quả là D[i−1][c]. Nếu lấy và c>=w[i], phải ghép nó với các món trước, nên ứng viên là D[i−1][c−w[i]]+v[i]. Lấy max hai trường hợp.

Điểm quan trọng là cả hai nhánh đều đọc hàng i−1 trong bản 0/1. Hàng đó chưa được phép dùng món thứ i, nên ghép thêm một lần không thể vô tình lấy lặp cùng món. Với i=0, không có món nào và mọi sức chứa cho giá trị 0 khi cho phép bỏ trống túi.

Hàng cuối tại c=6 cho giá trị 8 từ hai món khối lượng 4 và 2. Tại c=7, phương án 3+4 vẫn thắng. Không nhất thiết phải lấp đầy mọi sức chứa trung gian; D là tối ưu với điều kiện không vượt, nên các ô có thể lấy cùng một tập món nhẹ hơn c.

Giảm còn một mảng: vì sao 0/1 phải duyệt ngược?

Ta muốn ghi đè hàng cũ bằng hàng mới ngay trong d[c]. Khi cập nhật từ c lớn xuống nhỏ, ô d[c−w] nằm ở vị trí nhỏ hơn chưa được sửa trong lượt của món hiện tại. Nó vẫn là dữ liệu hàng trước, đúng yêu cầu D[i−1][c−w].

Phản ví dụ nhỏ: chỉ có một món khối lượng 2 giá trị 3, W=4. Nếu duyệt xuôi, ở c=2 ta gán d[2]=3, rồi c=4 đọc ngay d[2] vừa sửa để thành 6. Chương trình đã lấy cùng món hai lần. Duyệt ngược giữ d[2] cũ bằng 0 lúc tính d[4], nên chỉ cho giá trị 3.

Chiều vòng lặp không phải mẹo thuộc lòng độc lập với ý nghĩa trạng thái. Nó là cách giữ những ô cần đọc thuộc hàng trước dù hai hàng dùng chung vùng nhớ. Nếu sử dụng hai mảng old và new tách biệt, ta có thể duyệt c theo chiều khác mà vẫn đọc đúng old.

Không giới hạn: vì sao cần dữ liệu hàng hiện tại?

Nếu được lấy loại i nhiều lần, nhánh lấy món ghép với kết quả vẫn cho phép dùng loại i. Công thức dùng D[i][c−w]+v, không phải chỉ D[i−1][c−w]+v. Vì thế khi dùng một mảng, duyệt c tăng để ô nhỏ hơn đã chứa kết quả có thể dùng cùng loại hiện tại.

Với một loại khối lượng 2 giá trị 3 và sức chứa 4, c=2 cho 3 rồi c=4 dùng lại kết quả đó cho 6. Lần này việc lặp món chính là điều đề cho phép. Cùng một quá trình cập nhật từng là lỗi ở bản 0/1 lại trở thành chủ đích ở bản không giới hạn.

Khối lượng phải dương trong code. Một loại khối lượng 0, giá trị dương và không giới hạn làm giá trị tối ưu không bị chặn; vòng lặp hữu hạn không mô tả được đáp án này. Không thể xử lý chỉ bằng việc cho w=0 chạy qua công thức thông thường.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
long long solve(const vector<pair<int,int>>& items,int capacity,bool unlimited){
    vector<long long> d(capacity+1,0);
    for(auto [w,v]:items){
        if(unlimited){
            for(int c=w;c<=capacity;++c)d[c]=max(d[c],d[c-w]+v);
        }else{
            for(int c=capacity;c>=w;--c)d[c]=max(d[c],d[c-w]+v);
        }
    }
    return d[capacity];
}
int main(){
    int n=3,capacity=7;vector<pair<int,int>> items={{3,4},{4,5},{2,3}};
    if(cin>>n>>capacity){items.resize(n);for(auto& [w,v]:items)cin>>w>>v;}
    cout<<solve(items,capacity,false)<<' '<<solve(items,capacity,true)<<'\n';
}

import sys

def solve(items,capacity,unlimited=False):
    d=[0]*(capacity+1)
    for w,v in items:
        indices=range(w,capacity+1) if unlimited else range(capacity,w-1,-1)
        for c in indices:
            d[c]=max(d[c],d[c-w]+v)
    return d[capacity]

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    items=[(3,4),(4,5),(2,3)];capacity=7
    if a:
        n,capacity=a[:2]
        items=[tuple(a[2+2*i:4+2*i]) for i in range(n)]
    print(solve(items,capacity),solve(items,capacity,True))

Không nhập dữ liệu, chương trình in 9 10, lần lượt bản 0/1 và không giới hạn. Input riêng có n, capacity rồi n dòng w v. Mỗi dòng là một món trong bản 0/1, hoặc một loại trong bản không giới hạn. Điều kiện: n, capacity không âm; w nguyên dương; v nguyên không âm. Các giá trị và tổng cần dùng phải vừa long long trong C++.

Một hàm nhận cờ unlimited để chọn chiều vòng lặp. Hàm không sửa danh sách items; hai lượt chạy có mảng d riêng nên kết quả bản thứ nhất không làm bẩn bản thứ hai. Khi n=0 hoặc sức chứa 0, kết quả 0 trong cả hai mô hình.

Hai món khác nhau có cùng w,v vẫn là hai món có thể lấy riêng trong bản 0/1. Loại trùng dữ liệu một cách tùy ý sẽ làm mất số lượng thực sự được phép lấy. Với không giới hạn, loại giống hệt nhau có thể gây công lặp nhưng không thay đáp án tối ưu.

Không vượt W khác phải đúng W

Code khởi tạo mọi d[c]=0 vì một túi rỗng là lựa chọn hợp lệ cho điều kiện không vượt c. Nếu đề yêu cầu tổng khối lượng đúng c, chỉ d[0]=0 có thể đạt ban đầu, còn các c>0 phải mang dấu không thể đạt, chẳng hạn âm vô cùng trong bài tối đa.

Khi chuyển từ một ô không thể đạt, không được cộng v rồi coi thành đáp án thật. Cần guard tương tự việc tránh cộng INF trong bài đường đi. Ví dụ chỉ có món nặng 2, cần đúng tổng 3: bản không vượt trả giá trị món đó, còn bản đúng 3 phải báo không thể đạt. Hai đề khác nhau ngay cả khi sức chứa và vật phẩm giữ nguyên.

Tương tự, nếu bắt buộc chọn ít nhất một món hoặc có giá trị âm, cơ sở phải được thiết kế theo yêu cầu. Ví dụ của bài cho phép bỏ trống và v không âm để tập trung vào khác biệt số lượng 0/1 với không giới hạn.

O(nW) là giả đa thức

Mỗi món quét tối đa W sức chứa, nên thời gian O(nW), bộ nhớ O(W) cho bảng tối ưu. W là giá trị số học của sức chứa, không phải số bit để viết nó. Một W rất lớn dù được nhập bằng vài chữ số vẫn đòi bảng khổng lồ; đây là lý do cận này thường được gọi giả đa thức.

Nếu tổng giá trị nhỏ hơn sức chứa rất nhiều, có thể đổi trạng thái: dp[value] là khối lượng nhỏ nhất để đạt giá trị đó. Nếu n nhỏ nhưng W lớn, vét hai nửa có thể là hướng khác. Chỉ có ít loại đặc biệt hoặc nhiều bản hữu hạn còn cần biến thể riêng. Không có một mảng capacity+1 giải tốt mọi phiên bản cái túi.

Đừng tối ưu một mảng rồi quên yêu cầu in món. Giá trị cuối chỉ cho biết tổng tốt nhất, không tự cho danh sách đã chọn. Truy vết cần giữ quyết định hoặc tái tính hợp lý; với bản ghi đè tại chỗ, thông tin cha ngây thơ có thể tham chiếu trạng thái đã bị thay đổi.

Kiểm bằng liệt kê số lượng trên dữ liệu nhỏ

Để tự kiểm tra trên dữ liệu nhỏ (n ≤ 10), bạn có thể viết hàm quay lui thử mọi tập lấy/bỏ cho bài toán 0/1, hoặc thử mọi số lượng từ 0 đến capacity // w cho từng món ở bài toán không giới hạn. Cách vét cạn này không phụ thuộc vào chiều duyệt mảng dp, giúp bắt ngay lỗi quét nhầm chiều tiến/lùi.

Các ca có sức chứa 0, không có món, món quá nặng, giá trị 0, các món trùng và phản ví dụ một món nặng 1 được phép lấy một hay nhiều lần. Khi tự chạy, hãy bắt đầu bằng đúng một món và W đủ lấy hai lần; nếu hai bản cho cùng kết quả trong mọi ca như vậy, có thể bạn chưa thực sự phân biệt luật dùng lại.

Luyện ngay trên Big-O Coding

Hai bài 0/1 giúp kiểm chiều giảm và cơ sở. Bài không giới hạn yêu cầu chuyển sang chiều tăng với đúng ý nghĩa hàng hiện tại. Sau khi làm, tạo cùng một input nhỏ cho cả hai chương trình và giải thích vì sao đáp án có thể khác, thay vì chỉ nhớ đổi một dấu trong vòng for.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Knapsack
• CP-Algorithms: Introduction to DP
• C++ reference: vector