做网站要在vs安装什么,seo网站建设步骤,计算机编程是做网站,请网络推广外包公司有用吗多重背包I
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件#xff0c;每件体积是 vi#xff0c;价值是 wi。
求解将哪些物品装入背包#xff0c;可使物品体积总和不超过背包容量#xff0c;且价值总和最大。 输出最大价值。
输入格式 第一行两个整数每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式 输出一个整数表示最大价值。
数据范围 0N,V≤100 0vi,wi,si≤100 输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例 10
分析
多重背包问题是背包问题的变形可简化为01背包问题例
#include bits/stdc.h
using namespace std;
const int N1010;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main(){cinnm;for(int i1;in;i)cinw[i]v[i]s[i];for(int i1;in;i){for(int j1;jm;j){//j为背包容量 //完全背包和多重背包都用正序因为用的是第i层的数据 如果逆序的话f[i][j-w[i]]为0 for(int k0;ks[i];k){if(k*w[i]j)f[i][j]max(f[i][j],f[i-1][j-k*w[i]]k*v[i]);//k0时右边为f[i-1][j] //之后再比较k1,k2...就用f[i][j]与 f[i-1][j-k*w[i]]k*v[i]}}}coutf[n][m]endl;return 0;
}
