题目链接:https://www.acwing.com/problem/content/4/
题目描述:
解题思路:与前两个背包问题类似(题目链接:https://www.cnblogs.com/ygsr/p/14502222.html)
与前两个题比,这个题多添加一个for循环用来读取物品个数。
k*w[i]+list[i-1][j-k*v[i]] 这条语句的意思是:先将k个物品i放入表中然后剩余容量用表中前一个物品的价值填充。
源代码:
#include<iostream> #include<algorithm> #include<string.h> using namespace std; int list[105][105]; int v[105], w[105],s[105]; int main() { int n,m,t=0; cin >> n >> m; memset(list,0,n*n*4);//初始化 for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]>>s[i]; for (int i = 1; i <= n; i++)//件数 { for (int j = 1; j <=m; j++)//容量 { list[i][j] = list[i-1][j]; for (int k = 0; k <= s[i]; k++)//个数 { if (j >= k * v[i])//空间够就放入物品 { list[i][j] = max(list[i][j],k*w[i]+list[i-1][j-k*v[i]]); } } } } cout << list[n][m]; return 0; }