Submission #693347

#	Time	Username	Problem	Language	Result	Execution time	Memory
693347		hanlulu	Knapsack (NOI18_knapsack)	C++14	73 / 100	224 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std; 
const int MOD = 1e9+7;
int main()
{
  	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("snakes.in","r",stdin);
	//freopen("snakes.out","w",stdout);
 	int s,n;
 	cin >> s >> n;
 	vector<int> v(n+1),w(n+1),k(n+1);
 	for (int i = 1; i<=n; i++) 
 	{
 		cin >> v[i] >> w[i] >> k[i];
		k[i] = min(k[i],s/w[i]);	
	}
	vector< vector<int> > dp(n+1,vector<int>(s+1,0));

	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= s; j++)
	{
		for (int c = 0; c <= k[i] && c*w[i] <= j;c++) 
		{
			//选c个物品i
			dp[i][j] = max(dp[i][j], dp[i-1][j- c*w[i]] + c*v[i]);	
		}	
	} 
	cout << dp[n][s] << '\n';
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27