โปรแกรม C++ แก้ปัญหา 0-1 Knapsack

ในปัญหา 0-1 Knapsack มีชุดของรายการ แต่ละรายการมีน้ำหนักและค่า เราต้องกำหนดจำนวนของแต่ละรายการที่จะใส่ในชุด เพื่อให้น้ำหนักรวมน้อยกว่าหรือเท่ากับขีดจำกัดที่กำหนด และค่ารวมมากที่สุด

Input

Value = [10, 20, 30, 40, 60, 70]
Weight = [1, 2, 3, 6, 7, 4]
int w = 7

Output

knapsack value is: 100

อัลกอริทึม

Begin
    Input: ชุดรายการแต่ละอย่างมีน้ำหนักและค่า
    กำหนดความจุกระเป๋า
    จำนวนรายการ = sizeof(values) / sizeof(values[0])
    Knapsack(Values (เก็บในอาร์เรย์ v), Weights (เก็บในอาร์เรย์ w), จำนวนรายการที่แตกต่างกัน (n), ความจุกระเป๋า W)
    ถ้า (w < 0) Return
    ถ้าไม่มีรายการเหลือหรือความจุกลายเป็น 0 Return 0
    รวมรายการปัจจุบัน n ใน knapSack (v[n]) และ recurr สำหรับรายการที่เหลือ (n - 1) ด้วยความจุลดลง (W - w[n])
    แยกรายการปัจจุบัน n ออกจาก knapSack และ recurr สำหรับรายการที่เหลือ (n - 1)
    Return ค่าสูงสุดที่ได้จากการรวมหรือแยกรายการปัจจุบัน
End

ตัวอย่างโค้ด

#include <iostream>
#include <climits>
using namespace std;

int knapSack(int v[], int w[], int n, int W) {
    if (W < 0)
        return INT_MIN;
    if (n < 0 || W == 0)
        return 0;
    int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
    int ex = knapSack(v, w, n - 1, W);
    return max(in, ex);
}

int main() {
    int v[] = { 10, 20, 30, 40, 60, 70 };
    int w[] = { 1, 2, 3, 6, 7, 4 };
    int W = 7;
    int n = sizeof(v) / sizeof(v[0]);
    cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
    return 0;
}

ผลลัพธ์

Knapsack value is 100