คำชี้แจงปัญหา
กำหนดอาร์เรย์ขององค์ประกอบ N และผลรวม เราจำเป็นต้องหาขนาดของชุดย่อยขนาดสูงสุดที่ผลรวมเท่ากับผลรวมที่กำหนด
ตัวอย่าง
หากอาร์เรย์อินพุตเป็น arr ={ 2, 3, 5, 10 } และ sum =20 เอาต์พุตจะเป็น 4 เป็น −
2 + 3 + 5 + 10 =20 ซึ่งเท่ากับผลรวมที่กำหนด
อัลกอริทึม
เราสามารถใช้โปรแกรมไดนามิกเพื่อแก้ปัญหานี้ได้
ในการนับเซตย่อยสูงสุด เราใช้อาร์เรย์ DP อื่น (เรียกว่า 'นับอาร์เรย์') โดยที่การนับ[i][j] คือค่าสูงสุดของ
- นับ[i][j-1]. ไม่พิจารณาองค์ประกอบปัจจุบันที่นี่
- scount[i- X][j-1] + 1 โดยที่ X คือค่าขององค์ประกอบปัจจุบันที่เลือกสำหรับเซตย่อย
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int isSubsetSum(int set[], int n, int sum) {
bool subset[sum + 1][n + 1];
int count[sum + 1][n + 1];
for (int i = 0; i <= n; i++) {
subset[0][i] = true;
count[0][i] = 0;
}
for (int i = 1; i <= sum; i++) {
subset[i][0] = false;
count[i][0] = -1;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
subset[i][j] = subset[i][j - 1];
count[i][j] = count[i][j - 1];
if (i >= set[j - 1]) {
subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
if (subset[i][j]) {
count[i][j] = max(count[i][j - 1], count[i - set[j - 1]][j - 1] + 1);
}
}
}
}
return count[sum][n];
}
int main() {
int set[] = { 2, 3, 5, 10 };
int sum = 20;
int n = 4;
cout<< "Result = " << isSubsetSum(set, n, sum) << endl;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Result = 4
