建设项目审批后公示在哪个网站,建设部网站备案,东圃那里有做网站设计的,网站开发实验室问题描述
有 N 件物品和一个体积为 M 的背包。第 i 个物品的体积为 vi#xff0c;价值为 wi。每件物品可以使用无限次。
请问可以通过什么样的方式选择物品#xff0c;使得物品总体积不超过 M 的情况下总价值最大#xff0c;输出这个最大价值即可。
输入格式
第一行…问题描述
有 N 件物品和一个体积为 M 的背包。第 i 个物品的体积为 vi价值为 wi。每件物品可以使用无限次。
请问可以通过什么样的方式选择物品使得物品总体积不超过 M 的情况下总价值最大输出这个最大价值即可。
输入格式
第一行输入两个正整数 N,M。(1≤N,M≤1000)
接下来 N 行每行输入两个整数 vi,wi。(0≤vi,wi≤1000)
输出格式
输出一个整数表示符合题目要求的最大价值。
样例输入
4 5
1 2
2 4
3 4
4 5样例输出
10说明
你可以选择 1 个第一个物品和 2 个第二个物品。 #includeiostream
#includealgorithm
using namespace std;const int N 1e310;
int n, m;
int v[N], w[N];
int dp[N]; //dp[j]表示背包容量为j时的最大价值int main()
{cinnm;for(int i1; in; i) cinv[i]w[i];for(int i1; in; i) //遍历每个物品{//内层循环从v[i]到m正向遍历这使得同一物品可以被多次选取for(int jv[i]; jm; j){//dp[j]不选当前物品//dp[j - v[i]] w[i]选当前物品dp[j] max(dp[j], dp[j-v[i]] w[i]);}}coutdp[m];return 0;
}
