多重背包问题 I
有 NN 种物品和一个容量是 VV 的背包。
第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000<N,V≤100
0<vi,wi,si≤1000<vi,wi,si≤100
输入样例
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
其实代码没什么特别多说的，这些都是板子题，还是需要大家多练。
AC：
#include <iostream> #include <algorithm> using namespace std ; const int N = 110 ; int n, m ; int v[N], w[N] ,s[N] ; int f[N][N] ; int main() { cin >> n >> m ; for(int i=1; i<=n; i++) { cin >> v[i] >> w[i] >> s[i] ; } for(int i=1; i<=n; i++) { for(int j=0; j<=m; j++) { for(int k=0; k<=s[i] && k*v[i]<=j; k++) { f[i][j] = max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k) ; } } } for(int i=1; i<=n; i++) { for(int j=0; i<=m; j++) { for(int k=0; k<=s[i] && k*v[i]<=j; k++) { f[i][j] = max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k) ; } } } cout << f[n][m] << endl ; return 0 ; }
多重背包问题 II
有 NN 种物品和一个容量是 VV 的背包。
第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤10000<N≤1000
0<V≤20000<V≤2000
0<vi,wi,si≤20000<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。
输入样例
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例
10
AC:
#include <iostream> #include <algorithm> using namespace std ; const int N = 12010, M = 2010 ; int n , m; int v[N], w[N] ; int f[M] ; int main() { cin >> n >> m ; int cnt = 0 ; for(int i=1; i<=n; i++) { int a, b ,s ; cin >> a >> b >> s ; int k = 1 ; while(s>=k) { cnt++ ; v[cnt] = a*k ; w[cnt] = b*k ; s-=k ; k*=2 ; } if(s>=0) { cnt++ ; v[cnt] = a*s ; w[cnt] = b*s ; } } n = cnt ; for(int i=1; i<=n; i++) { for(int j=m; j>=v[i]; j--) { f[j] = max(f[j], f[j-v[i]]+w[i]) ; } } cout << f[m] << endl ; return 0 ; }
好了，今天就向大家分享这两个简单的板子题，当然背包问题还有更多板子，如果大家需要详细解答的话，可以在文章下面给我留言，这样我会将这两个题以及之后的推荐算法题都向大家做一个讲解的。
