思路：动态规划的背包问题。建立二维数组dp[i][j]表示前i个物品不超过j元物品的价格与重要度乘积的总和的最大值。dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+V[i]*W[i]) 特殊情况：当j<v[i]时，dp[i][j]=dp[i-1][j]。注意：可
展开全文
看了一下题解里没有写就地滚动的（虽然这题很简单） 那就来一个吧 简单01背包：开心的金明 传送门 题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一
展开全文
还是一个背包问题。只是在这里需要计算的价值变成了每件物品的价格与重要度的乘积。
但是由于价格和重要度的乘积的总和较大，所以采用离散化的方式去减少空间。由于没有结果的不需要记录，如果当前选的结果还没有之前没选的大也不用更新。
使用map去保存从而减少的空间。
#include&nb
展开全文
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30010;
ll dp[26][N];
struct ty{
int v,imp;
ll sum;
}a[N
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
