【Acwing】背包

01背包

#include 
#define min3(x , y , z) min(x , min(y , z))
#define max3(x , y , z) max(x , max(y , z))

using namespace std ;

typedef long long LL ;
typedef double LF ;
const int N = 1010 ;
int n , m ;
int w[N] , v[N] , f[N] ;
void fun () {
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= w[i]; j--)
			f[j] = max (f[j] , f[j - w[i]] + v[i]) ;
}

int main ()
{


	cin >> n >> m ;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i] ;
	fun () ;
	cout << f[m] ;



	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

完全背包

#include 
#define min3(x , y , z) min(x , min(y , z))
#define max3(x , y , z) max(x , max(y , z))

using namespace std ;

typedef long long LL ;
typedef double LF ;
const int N = 1010 ;
int n , m ;
int w[N] , v[N] , f[N] ;
void fun () {
	for (int i = 1; i <= n; i++)
		for (int j = w[i]; j <= m; j++)
			f[j] = max (f[j] , f[j - w[i]] + v[i]) ;
}

int main ()
{


	cin >> n >> m ;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i] ;
	fun () ;
	cout << f[m] ;



	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

多重背包I

#include 
#define min3(x , y , z) min(x , min(y , z))
#define max3(x , y , z) max(x , max(y , z))

using namespace std ;

typedef long long LL ;
typedef double LF ;
const int N = 110 ;
int n , m ;
int w[N] , v[N] , s[N] , f[N] ;
void fun () {
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= 0; j--)
			for (int k = 0; k <= s[i]; k++)
				if (j >= w[i] * k)
					f[j] = max (f[j] , f[j - k * w[i]] + k * v[i]) ;
}

int main ()
{


	cin >> n >> m ;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i] >> s[i] ;
	fun () ;
	cout << f[m] ;



	return 0 ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

多重背包II

#include 
#define min3(x , y , z) min(x , min(y , z))
#define max3(x , y , z) max(x , max(y , z))

using namespace std ;

typedef long long LL ;
typedef double LF ;
const int N = 100010 ;
int n , m ;
int w[N] , v[N] , f[N] ;
int _w , _v , _s , tot ;
void fun () {
	for (int i = 1; i <= tot; i++)
		for (int j = m; j >= w[i]; j--)
			f[j] = max (f[j] , f[j - w[i]] + v[i]) ;
}

int main ()
{


	cin >> n >> m ;
	while (n -- ) {
		cin >> _w >> _v >> _s ;
		for (int i = 1; ; i *= 2) {
			if (_s < i)
				break ;
			_s -= i , w[++ tot] = _w * i , v[tot] = _v * i ;
		}
		if (_s > 0)
			w[++ tot] = _w * _s , v[tot] = _v * _s ;
	}
	fun () ;
	cout << f[m] ;



	return 0 ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

多重背包III

#include 
#define min3(x , y , z) min(x , min(y , z))
#define max3(x , y , z) max(x , max(y , z))

using namespace std ;

typedef long long LL ;
typedef double LF ;
const int N = 20010 ;
int pre[N] , f[N] , q[N] ;
int n , m , v , w , s ;

int main ()
{


    cin >> n >> m ;
    for (int i = 1; i <= n; i++) {
        memcpy (pre , f , sizeof (f)) ;
        cin >> v >> w >> s ;
        for (int j = 0; j < v; j++) {
            int head = 0 , tail = - 1 ;
            for (int k = j; k <= m; k += v) {
                if (head <= tail && k - s * v > q[head])
                    head ++ ;
                while (head <= tail && pre[q[tail]] - (q[tail] - j) / v * w <= pre[k] - (k - j) / v * w)
                    tail -- ;
                if (head <= tail)
                    f[k] = max (f[k] , pre[q[head]] + (k - q[head]) / v * w) ;
                q[++ tail] = k ;
            }
        }
    }
    cout << f[m] ;



	return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39