Coin thay đổi với số lượng hạn chế của tiền kim loại

Question

Tôi đã viết một chương trình để tạo ra các tập hợp con sum mà có thể được sử dụng trong vấn đề này trong đó nêu:

Giả sử, bạn có 3 $ 1 tiền xu, 2 $ 2 tiền xu, 3 $ 5 xu, 1 $ 10 đồng xu, có 4 cách để nhận 10 đô la từ những đồng tiền đó. Nếu có n1 $ X1 đồng xu, đồng xu n2 $ X2 .... nm $ Xm xu, chúng ta có thể nhận được bao nhiêu cách $ X từ số tiền giới hạn này?

Nếu chúng tôi tạo bộ {X1, X1 ..... X1, X2, X2 .......... X2, ..., ..., .... ........, Xm, Xm ... Xm}, và sau đó chạy tập hợp con tổng hợp trên nó, chắc chắn chúng ta có thể nhận được kết quả cho $ X. Nhưng tôi không thể tìm cách sử dụng các bộ {n1, n2, n3 .... nm}, {X1, X2, X3 .... Xm}. Một người bạn nói với tôi rằng đó là một biến thể của vấn đề ba lô, nhưng tôi không chắc chắn, làm thế nào.

Đây là một mã một phần của những gì tôi đã viết:

ways[0]=1, mylim=0; 
for(i=0;i<count;i++){ 
    if(mylim+coins[i]<=LIMIT) mylim+=coins[i]; 
    else mylim=LIMIT; 

    for(j=mylim; j>=coins[i];j--){ 
     ways[j]=(ways[j]+ways[j-coins[i]])%MOD; 
    } 
} 

Nó sẽ là tuyệt vời đối với tôi nếu bạn là loại, đủ để giải thích một chút công phu.

EDIT: Câu hỏi này phù hợp hơn cho stackexchange cho khoa học máy tính, nhưng vì đây là câu hỏi cũ của tôi, tôi thích chỉnh sửa ở đây.

Vấn đề này có thể được giải quyết với loại trừ nguyên tắc Bao gồm, và nó đi kèm tiện dụng khi chúng ta có giá trị đồng tiền cố định nhưng số lượng mỗi đồng xu khác nhau với mỗi truy vấn.

Giả sử, cách [v] là cách làm $ v với $ x1, $ x2, .. $ xm, mỗi đang được sử dụng nhiều lần khi cần thiết. Bây giờ, nếu chúng ta đang sử dụng chỉ n1 số $ x1, chúng ta phải trừ đi các cấu hình sử dụng ít nhất (n1 + 1) số lượng $ x1 (mà thực chất là cách [v - (n1 + 1) x1]). Hơn nữa, nếu chúng ta đang sử dụng chỉ n2 số $ x2, chúng ta phải trừ cách [v - (n2 + 1) x2] là tốt, và vv

Bây giờ, chúng tôi có hai lần trừ các cấu hình có ít nhất (n1 + 1) $ x1 và (n2 + 1) $ x2 được sử dụng, do đó chúng ta cần thêm cách [v - (n1 + 1) x1 - (n2 + 1) x2] và v.v.

Đặc biệt, nếu,

N = tập các cấu hình mà tất cả các đồng tiền được sử dụng càng nhiều càng tốt,

Ai = tập các cấu hình có ít nhất ni + 1 số của $ xi được sử dụng, cho 1 < = i < = m, sau đó

kết quả chúng tôi đang tìm kiếm = | N | - | A1 | - | A2 | .. - | Am | + | A1 và A2 | + | A1 và A3 | + ... - | A1 và A2 và A3 | .....

Mã mà tính số cấu hình với tiền xu không giới hạn thực sự là đơn giản:

ways[0]=1; 
for(int i = 0 ; i < count ; i++){ 
    for(int j = coins[i] ; j < ways.size() ; j++){ 
     ways[j] += ways[j-coins[i]]; 
    } 
} 

Answer 1

Giả sử tất cả các bạn ni là 1.

Hãy để ways[j] = number of ways of obtaining sum j.

Bạn có thể tính toán điều này như vậy (đây là những gì bạn đang làm, nhưng tôi không biết tại sao bạn đặt tên biến là primes).

ways[0] = 1 
for i = 1 to m do 
    for j = myLim downto X[i] do 
     ways[j] += ways[j - X[i]]; 

Điều này có nghĩa là bạn chỉ sử dụng mỗi đồng xu có giá trị Xi một lần. Bạn có thể thêm vòng lặp khác để sử dụng nó ít nhất một lần và nhiều nhất tuy nhiên ni lần:

ways[0] = 1 
for i = 1 to m do 
    for times = 1 to n[i] do // use Xi one time, then two times, then three, ..., then ni 
     for j = myLim downto times*X[i] do 
      ways[j] += ways[j - times*X[i]]; 

Bạn vẫn có thể áp dụng modulo của bạn và tính toán giới hạn của bạn, tôi rời những người ra vì đơn giản.

Answer 2

Vấn đề được đặt tên là "Vấn đề đồng tiền" và được biết đến là NP-hard.

Bạn có thể tìm hiểu một chút về nó here.