解题思路:经典的动态规划问题.
我的理解:本题加入了参数s,表示一个物体最多可以买多少件,其实就相当于是01背包中,多加入了几个相同的物体,所以这道题实质上和第2131题:01背包是一样的.
注意事项:本题由于数据量较大,用最普通的dp数组,会出现一个问题:空间不够,所以就要想办法优化dp数组.
有两个办法:1.重复利用一个数组 2.滚动利用数组
重复利用一个数组的方法好像已经有人说了,那我就来说说更好理解的滚动利用数组的办法;
参考代码:
#include<bits/stdc++.h> using namespace std; int W[5005],V[5005]; //价格和价值 //waste value int w,v,s; //价格,价值,最大数量 int n; //相当于01背包中,有n件物品 int M,N; //Money拨款金额 Number礼物种类 int i,j; int dp[2][5000005]; //普通dp数组dp[i][j]的含义:在前i件物品中取价格为j时的最大总价值 //这里是滚动利用dp数组 int main() { scanf("%d %d",&N,&M); //这里的N我们之后不会用到,M会用到 getchar(); while(scanf("%d %d %d",&w,&v,&s) != EOF) { while(s) //转化为01背包 { s--; i++; W[i] = w; V[i] = v; } } n = i; //相当于01背包中,有n件物品 for(i = 1; i <= n; i++) { for(j = 1; j <= M; j++) { if(j < W[i]) { dp[i & 1][j] = dp[(i-1) & 1][j]; /*注意这里的 &i,就是数组的滚动利用*/ /*当i为奇数,i的二进制最低位上是1,进行&1操作后得1, 当i为奇数,i的二进制最低位上是0,进行&1操作后得0;*/ /*可以结合下图理解*/ } else { dp[i & 1][j] = max(dp[(i-1) & 1][j-W[i]] + V[i], dp[(i-1) & 1][j]); } } } cout << dp[n & 1][M]; //n如果为奇数 ,n&1就等于1; 为偶数就等于0 //而如果n为奇数,滚动数组刚好就停在下面一行(dp[1][]),如果为偶数就在上面一行(dpp[0][]) //故运算契合需求 return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1007 |
数列 (C++代码)浏览:664 |
C语言训练-字符串正反连接 (C语言代码)浏览:616 |
C语言训练-求素数问题 (C语言代码)浏览:1446 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:522 |
A+B for Input-Output Practice (III) (C语言代码)浏览:569 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:575 |
WU-格式化数据输出 (C++代码)浏览:1186 |
WU-判定字符位置 (C++代码)浏览:1395 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:531 |