背包问题有前提

本文主要是介绍背包问题有前提，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：这个有大前提的背包感觉不能用二进制拆分，不然搞不清楚

注意三维的顺便，第一维度是枚举物品，第二维度是倒序枚举空间，第三维度是枚举数量

---

题目地址

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N = 305;
int cost[N];int val[N];
int n,x;
int dp[500];
int att[N],price[N],c[N],gra[N],lmax[N];signed main(){cin >> n >> x;for(int i=1;i<=n;i++){cin >> att[i] >> price[i] >> c[i] >> gra[i] >> lmax[i];}for(int i=1;i<=n;i++){for(int j=x;j>=price[i];j--){for(int k=0;price[i]+k*c[i]<=j && k <=lmax[i];k++){dp[j] = max(dp[j],dp[j-(price[i]+k*c[i])] + att[i] + k*gra[i]);}}}cout << dp[x];return 0;
}

这篇关于背包问题有前提的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---