题意

有 $n$ 个物品， $m$ 块钱。

每个物品有一个重量（价值）$w$，价值 $v$，数量 $s$

思路

本题和A1267. 【例9.11】01背包问题的思路差不多，只是物品变成多个了（多一个循环遍历数量）

详见题解 - 【例9.11】01背包问题

01 背包是背包的基础，这里的做法是在 01 背包的基础上增加数量遍历

代码

#include <bits/stdc++.h>
using namespace std;
int a[6005],w[505],v[505],s[505];
// a：第 i 个重量（价格）
// w：第 i 个奖品的重量（价格）
// v：第 i 个奖品的价值
// s：第 i 个奖品的数量
int main(int argc, char **argv){
	int n,m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		cin >> w[i] >> v[i] >> s[i];
	}
	for (int j = 1;j <= n;j++){
		for (int i = m;i >= w[j];i--){
			for (int k = 1;k <= s[j] && k * w[j] <= i;k++){	// 遍历这个奖品的数量，且总重量不能超过最大重量
				a[i] = max(a[i - k * w[j]] + k * v[j],a[i]);	// 01 背包是只加一个，这里要加数量 * 价值
			}
		}
	}
	cout << a[m];
	return 0;
}

广告

Mօjang AB 开发的《你的mc打怪记》，是一个 mc 版的打怪小游戏，欢迎大家游玩。

在末影龙统治的世界里，你要击败末影龙，拯救人类，成为新的统治者。

点我进入《你的mc打怪记》主页

#define ll long long
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[100005],w[100005],s[100005];
int vst[100005];
//递推数组 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
	for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=0;k<=s[i]&&!(j-k*v[i]<0);k++)
		vst[j]=max(vst[j],vst[j-k*v[i]]+k*w[i]);
	/*i:遍历数组v 
	  j:反向遍历递推数组
	  k:次数计时器
	  在循环途中，若内存不足放入背包(j-k*v[i]<0) 
	  退出当前次数计时
	*/ 
	cout<<vst[m]<<"\n";
	//输出最后的visit 
	return 0;
}

记忆搜索再起不能