转化为01背包的做法,在01背包的基础上加上一个for循环表示第i个物品装0->c[i]个即可
参考代码:
#include<iostream> using namespace std; const int M = 10000; int n, m; int dp[M], w[M], v[M], c[M]; int main(){ cin>>n>>m; for(int i = 0; i < n; i++){ cin>>w[i]>>v[i]>>c[i]; } for(int i = 0; i < n; i++){ for(int j = m; j >= 0; j--){ for(int k = 0; k <= c[i]; k++){ if(j >= w[i] * k){ dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]); } } } } cout<<dp[m]; return 0; }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:441 |
C语言程序设计教程(第三版)课后习题6.5 (Java代码)浏览:1111 |
简单的a+b (C语言代码)浏览:548 |
C语言训练-求函数值 (C语言代码)浏览:931 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:624 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:517 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1146 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:858 |
用筛法求之N内的素数。 (C++代码)浏览:692 |
母牛的故事 (C语言代码)浏览:549 |