解题思路:转化为完全背包, 当数量不限时,数量为背包容量除以物品体积
注意事项:滚动数组优化, j 从m 到 w[i]
参考代码:
#include<iostream> #include<algorithm> using namespace std; const int N = 2e2 + 10; int f[N],w[N],c[N],p[N]; int main() { int n, m; cin >> m >> n; for(int i = 1; i <= n; i ++){ cin >> w[i] >> c[i] >> p[i]; if (!p[i]) p[i] = m / w[i]; } for(int i = 1; i <= n; i ++) for(int j = m; j >= w[i]; j --) for(int k = 0; k <= p[i]; k ++) if(j >= k * w[i]) f[j] = max(f[j],f[j - k * w[i]] + k * c[i]); cout <<f[m]; return 0; }
0.0分
1 人评分
不会做的浏览:872 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:559 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:624 |
剪刀石头布 (C语言代码)浏览:1747 |
WU-小九九 (C++代码)浏览:1681 |
【求[X,Y]内被除3余1并且被除5余3的整数的和】 (C语言代码)浏览:672 |
链表数据求和操作 (C语言代码)浏览:941 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:762 |
简单的a+b (C语言代码)浏览:434 |
字符删除 (C语言代码)浏览:715 |