algorithm
क्लेश समस्या

टिप्पणियों

नैकपैक समस्या मूल बातें

समस्या : उन वस्तुओं के एक सेट को देखते हुए जहां प्रत्येक वस्तु में एक वजन और मूल्य होता है, एक संग्रह में शामिल करने के लिए प्रत्येक की संख्या निर्धारित करें ताकि कुल वजन किसी दिए गए सीमा से कम या बराबर हो और कुल मूल्य यथासंभव बड़ा हो ।

नैकस्पैक समस्या के लिए छद्म कोड

दिया हुआ:

1. मान (सरणी v)
2. भार (सरणी w)
3. विभिन्न मदों की संख्या (एन)
4. क्षमता (डब्ल्यू)

for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

पायथन का उपयोग करके उपरोक्त छद्म कोड का एक सरल कार्यान्वयन:

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

कोड चलाना: इसे knapSack.py नामक फ़ाइल में सहेजें

$ python knapSack.py
220

उपरोक्त कोड की समय जटिलता: O(nW) जहां n वस्तुओं की संख्या है और W O(nW) की क्षमता है।

समाधान # C में लागू किया गया

public class KnapsackProblem
{
    private static int Knapsack(int w, int[] weight, int[] value, int n)
    {
        int i;
        int[,] k = new int[n + 1, w + 1];
        for (i = 0; i <= n; i++)
        {
            int b;
            for (b = 0; b <= w; b++)
            {
                if (i==0 || b==0)
                {
                    k[i, b] = 0;
                }
                else if (weight[i - 1] <= b)
                {
                    k[i, b] = Math.Max(value[i - 1] + k[i - 1, b - weight[i - 1]], k[i - 1, b]);
                }
                else
                {
                    k[i, b] = k[i - 1, b];
                }
            }
        }
        return k[n, w];
    }

    public static int Main(int nItems, int[] weights, int[] values)
    {
        int n = values.Length;
        return Knapsack(nItems, weights, values, n);
    }
}