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

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

อินพุต

ค่า =[10, 20, 30, 40, 60, 70]น้ำหนัก=[1, 2, 3, 6, 7, 4]int w=7

ผลลัพธ์

ค่าเป้คือ:100

อัลกอริทึม

Begin Input:ชุดของแต่ละรายการที่มีน้ำหนักและค่า Set knapsack capacity Number of items=sizeof(values) / sizeof(values[0]) Knapsack(Values ​​(stored in array v), Weights (จัดเก็บไว้ในอาร์เรย์) w), จำนวนรายการที่แตกต่าง (n), ความจุเป้ W) ถ้า (w <0) ส่งคืน หากไม่มีรายการเหลือหรือความจุกลายเป็น 0 ส่งคืน 0 รวมรายการปัจจุบัน n ใน knapSack (v[n]) และเกิดขึ้นซ้ำสำหรับรายการที่เหลืออยู่ ( n - 1) ด้วยความจุที่ลดลง (W - w[n]) ยกเว้นรายการปัจจุบัน n จาก knapSack และเกิดขึ้นซ้ำสำหรับรายการที่เหลือ (n - 1) ส่งคืนค่าสูงสุดที่เราได้รับโดยการรวมหรือไม่รวม itemEnd ปัจจุบัน 
โค้ดตัวอย่าง
 
#include #include using namespace std;int knapSack(int v[], int w[], int n, int W) { if (W <0) return INT_MIN; ถ้า (n <0 || W ==0) คืนค่า 0; int ใน =v[n] + knapSack(v, w, n - 1, W - w[n]); int อดีต =knapSack(v, w, n - 1, W); คืนค่าสูงสุด (ใน อดีต);}int main () { int v[] ={ 10, 20, 30, 40, 60, 70 }; int w[] ={ 1, 2, 3, 6, 7, 4 }; int W =7; int n =ขนาดของ(v) / sizeof(v[0]); cout <<"ค่าเป้คือ" < 
ผลลัพธ์
 
ค่าเป้ 100