01 背包
每件物品只能选一次，容量必须倒序枚举。输入 n、容量 m，再输入每件物品的体积和价值。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m; cin >> n >> m;
vector<int> f(m+1);
for(int i=0;i<n;++i) {
int v,w; cin >> v >> w;
for(int j=m;j>=v;--j) f[j]=max(f[j],f[j-v]+w);
}
cout << f[m] << '\n';
}
完全背包
每件物品可重复选择，容量正序枚举；体积须为正数。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m; cin >> n >> m; vector<int> f(m+1);
for(int i=0;i<n;++i) {
int v,w; cin >> v >> w;
for(int j=v;j<=m;++j) f[j]=max(f[j],f[j-v]+w);
}
cout << f[m] << '\n';
}
二维费用 01 背包
输入物品数量、两种容量，再输入每件物品的两种费用与价值。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,V,M; cin >> n >> V >> M;
vector<vector<int>> f(V+1,vector<int>(M+1));
while(n--) {
int v,m,w; cin >> v >> m >> w;
for(int j=V;j>=v;--j) for(int k=M;k>=m;--k)
f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}
cout << f[V][M] << '\n';
}