深圳专业软件网站建设,Wordpress改邮箱,wordpress 邀请机制,网站建设需要报告题目
有 N N N种物品和一个容量是 V V V的背包#xff0c;每种物品都有无限件可用。 第 i i i 种物品的体积是 v i v_i vi#xff0c;价值是 w i w_i wi。 求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。输出最大…题目
有 N N N种物品和一个容量是 V V V的背包每种物品都有无限件可用。 第 i i i 种物品的体积是 v i v_i vi价值是 w i w_i wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。
输入格式 第一行两个整数 N N N V V V用空格隔开分别表示物品种数和背包容积。 接下来有 N N N 行每行两个整数 v i v_i vi, w i w_i wi用空格隔开分别表示第 i i i 种物品的体积和价值。 输出格式 输出一个整数表示最大价值。
分析
状态表示
用一个数组f[i][j]来表示只看前i个物品在总体积是j的情况下总价值最大是多少。 那么题目要求在背包容量为V的条件下从N件物品中选取物品使得的总价值最大状态表示应为f[N][V].
状态计算
在进行状态计算之前先得对状态做一个划分。对于01背包f[i][j]的状态只有两种
不选第i个物品选第i个物品f[i-1][j]f[i-1][j-v[i]] w[i]
取两种状态的最大值 对于完全背包物品可以取无限个不过k最多为v 那么状态可以划分为
不选第i个物品选0个选1个第i个物品选2个第i个物品…选k个第i个物品f[i-1][j]f[i-1][j-v[i]] w[i]f[i-1][j-2*v[i]] 2*w[i]…f[i-1][j-k*v[i]] k*w[i]
找到这些状态的最大值即可。 因此我们只需要在0-1背包的基础上多循环一次k
#includeiostream
using namespace std;const int N 1010;int n, m;
int f[N][N], v[N], w[N];int main(){cin n m;for(int i 1; i n; i )cin v[i] w[i];for(int i 1; i n; i )for(int j 0; j m; j )for(int k 0; k * v[i] j; k )f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k * w[i]);//求出每一个 f[i][j]cout f[n][m] endl;
}优化
上面的算法时间复杂度过高。 回顾下状态切分 对于f[i][j]来说
不选第i个物品选1个第i个物品选2个第i个物品选3个第i个物品f[i-1][j]f[i-1][j-v[i]] w[i]f[i-1][j-2*v[i]] 2*w[i]f[i-1][j-3*v[i]] 3*w[i]
而巧就巧在f[i][j-v[i]]的状态划分为
不选第i个物品选1个第i个物品选2个第i个物品f[i-1][j-v[i]]f[i-1][j-2*v[i]] w[i]f[i-1][j-3*v[i]] 2*w[i]
我们发现f[i][j]中选择1–k个第i个物品和f[i][j-v[i]]中选择k–1个第i个物品正好是对应的只相差w[i] 因此对于f[i][j]选择k个第i个物品的最大值为f[i][j-v[i]] w[i]我们不再需要循环k个物品了状态划分简化为
不选第i个物品选择k个第i个物品f[i-1][j]f[i][j-v[i]] w[i]
取二者的最大值即可。 代码
#includeiostream
#includealgorithm
using namespace std;
const int N 1002;
int n, m;
int f[N][N];
int v[N], w[N];int main(){cin n m;for (int i 1; i n; i) scanf(%d%d, v[i], w[i]);for (int i 1; i n; i) {for (int j 0; j m; j) {f[i][j] f[i-1][j];if (j v[i]) {f[i][j] max(f[i][j], f[i][j-v[i]] w[i]);}}}cout f[n][m] endl;return 0;
}
