Profitable Schemes
Problem (yeniden ifade)
group[i] üyeli ve profit[i] kârlı G suç. Toplam en fazla n üye. kâr ≥ minProfit olan şema sayısını döndür (mod 10^9+7). Boş şemanın kârı 0.
Sezgi
0/1 knapsack: kapasite üyeler ve tavanlı kâr (minProfit yeter). Yolları say.
Yaklaşımlar
2D knapsack (üyeler × kâr)
DoğrulanmadıZaman O(G·n·P)Alan O(n·P)
Fikir. dp[i][j], i üyeli ve kârı min(j, minProfit) olan yol sayısı. Her suç için ters yönde dolaş. dp[*][minProfit] topla.
Yürüyüş. n=5, minProfit=3, group=[2,2], profit=[2,3] → 2.
Trade-off. Durumu küçük tutmak için kâr boyutunu minProfit’te tavanla.
Çözüm
export function profitableSchemes(
n: number,
minProfit: number,
group: number[],
profit: number[],
): number {
const MOD = 1_000_000_007;
const dp = Array.from({ length: n + 1 }, () => Array(minProfit + 1).fill(0));
dp[0]![0] = 1;
for (let k = 0; k < group.length; k++) {
const members = group[k]!, p = profit[k]!;
for (let i = n; i >= members; i--) {
for (let j = minProfit; j >= 0; j--) {
const nj = Math.min(minProfit, j + p);
dp[i]![nj] = (dp[i]![nj]! + dp[i - members]![j]!) % MOD;
}
}
}
let ans = 0;
for (let i = 0; i <= n; i++) ans = (ans + dp[i]![minProfit]!) % MOD;
return ans;
}
export function profitableSchemes(
n: number,
minProfit: number,
group: number[],
profit: number[],
): number {
const MOD = 1_000_000_007;
const dp = Array.from({ length: n + 1 }, () => Array(minProfit + 1).fill(0));
dp[0]![0] = 1;
for (let k = 0; k < group.length; k++) {
const members = group[k]!, p = profit[k]!;
for (let i = n; i >= members; i--) {
for (let j = minProfit; j >= 0; j--) {
const nj = Math.min(minProfit, j + p);
dp[i]![nj] = (dp[i]![nj]! + dp[i - members]![j]!) % MOD;
}
}
}
let ans = 0;
for (let i = 0; i <= n; i++) ans = (ans + dp[i]![minProfit]!) % MOD;
return ans;
}
Şablon bağlantısı
Çok kısıtlı 0/1 knapsack sayma.
Yansıma
dp[k][p]: en fazla k kişi, en az p kâr. KârminProfit’te kesilir. Grup bir kez, döngü geriye.- Mod
10**9+7. Kişi veya kâr yetmeyen grup atlanır. - Grup yok: eşik 0 ise 1 (hiçbir şey yapmamak), değilse 0.