文章
20
粉丝
224
获赞
56
访问
137.4k
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
// 可以支配的钱数、清单上可选择的物品种类、输入物品的价格、输入物品的受欢迎程度、状态转移表
int M, N, v[1005], p[1005], dp[1005][105] = {0};
int main() {
while (~scanf("%d%d", &M, &N)) {
vector<int> buy[105]; // 每个受欢迎程度下所购买的物品列表
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= N; ++i) scanf("%d%d", &v[i], &p[i]);
// dp[i,j]代表前 i 个物品价格最大为 j 最高的受欢迎程度
// buy[j]代表在价格 j 下且受欢迎程度最大时所购买的物品列表
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= M; ++j) {
if (j - v[i] >= 0) {
// 当加上物品 i 比不加物品 i 的受欢迎程度大
if ((dp[i-1][j-v[i]] + p[i]) > dp[i-1][j]) {
buy[j] = buy[j-v[i]]; // 先等于不加物品 i 且受欢迎程度最大的物品列表
buy[j].push_back(i); // 接着再把物品 i 追加上去
dp[i][j] = dp[i-1][j-v[i]] + p[i];
} else dp[i][j] = dp[i-1][j];
}
else dp[i][j] = dp[i-1][j];
}
}
printf("%d\n", dp[N][M]);
if (dp[N][M] != 0) {
for (int i = 0; i < buy[...
登录后发布评论
暂无评论,来抢沙发