八月份杭州X02笔记整理~（3/3）

133****3286

2023-08-20 18:41:35

发布于：浙江

7阅读

0回复

0点赞

前两期跳转在这里第一部分第二部分

Part 1 01背包

二维模板

#include<iostream>
using namespace std;
const int MAXN = 2e3 + 10
const int N = 35;
int m, n;
int w[N], c[N];
int f[MAXN];
int main(){
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
	cin >> w[i] >> c[i];
    }
    for (int i=1; i <= n; i++) {
	for (int v = m; v >= w[i]; v--){
	    if (f[v-w[i]] + c[i] > f[v]){
		f[v] = f[v-w[i]]+c[i];
            }
        }
    }
    cout << f[m];
    return 0;
}

一维模板

#include<iostream>
using namespace std;
const int MAXN = 2e3  + 10;
const int N = 35;
int m, n;
int w[N], c[N];
int f[MAXN];
int main(){
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
	cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= n; i++){ 
        for (int v = m; v >= w[i]; v--){
	    if (f[v-w[i]]+c[i]>f[v]){
		f[v] = f[v-w[i]]+c[i];
            }
        }
    }
    cout << f[m];
    return 0;
}

Part 2 完全背包

二维模板

#include<iostream>
using namespace std;
const int MAXN = 2e3 + 10;
const int N = 35;
int m, n;
int w[MAXN], c[MAXN];
int f[MAXN][N];
int main(){
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
	cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= n; i++){
	for (int v = 1; v <= m; v++){
	    if (v < w[i]){
		 f[i][v] = f[i-1][v];
            }
	    else{
		if (f[i-1][v] > f[i][v-w[i]]+c[i]){
		    f[i][v] = f[i-1][v];
	        }
                else{
		    f[i][v] = f[i][v-w[i]]+c[i];
		}			
	    }
        }
    }
    cout << "max=" << f[n][m];
    return 0;
}

一维模板

#include <iostream>
using namespace std;
const int MAXN = 2e3 + 10;
const int N = 35;
int n,m,v,i;
int c[MAXN],w[MAXN];
int f[N];
int main(){
    cin >> m >> n;
    for(i = 1;i <= n;i++){
	cin >> w[i] >> c[i];
	for(i = 1;i <= n;i++){
	    for(v = w[i];v <= m;v++){
		if(f[v-w[i]] + c[i] > f[v]){ 
		    f[v] = f[v-w[i]] + c[i];
                }
            }
        }
    }
    cout << "max=" << f[m];
    return 0;
}