Pagini recente » Cod sursa (job #863251) | Cod sursa (job #1874739) | Cod sursa (job #177240) | Cod sursa (job #2067134) | Cod sursa (job #3225950)
#include <stdio.h>
#include <utility>
#include <algorithm>
#define N 17
#define MAX_MASK (1 << N)
#define INF (1 << 30)
unsigned int v[N];
std::pair <unsigned int, int> dp[MAX_MASK];
int n;
int main() {
FILE *fin, *fout;
int w;
fin = fopen("zebughil.in", "r");
fout = fopen("zebughil.out", "w");
for ( int q = 0; q < 3; q ++ ) {
fscanf(fin, "%d%d", &n, &w);
for ( int i = 0; i < n; i ++ )
fscanf(fin, "%d", &v[i]);
int max_mask = (1 << n) - 1;
dp[0] = {0, 0};
for ( int mask = 1; mask <= max_mask; mask ++ ) {
dp[mask] = {0, INF};
for ( int bit = 0; bit < n; bit ++ ) {
if ( ((mask >> bit) & 1) == 1 ) {
int prev = mask - (1 << bit);
if ( dp[prev].first + v[bit] <= w ) {
if ( dp[prev].second < dp[mask].second )
dp[mask] = {dp[prev].first + v[bit], dp[prev].second};
}
else if ( dp[prev].second + 1 < dp[mask].second )
dp[mask] = {std::min(v[bit], dp[prev].first), dp[prev].second + 1};
}
}
}
fprintf(fout, "%d\n", dp[max_mask].second + 1);
}
fclose(fin);
fclose(fout);
return 0;
}