华师一附中OI组

标题: P1060 开心的金明 [打印本页]

作者: admin 时间: 2018-5-11 11:31
标题: P1060 开心的金明
https://www.luogu.org/problemnew/show/P1060
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入输出格式
输入格式：
输入的第1行，为两个正整数，用一个空格隔开：N m（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数 v p（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）

输出格式：
输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

输入输出样例
输入样例#1：
1000 5
800 2
400 5
300 5
400 3
200 2
输出样例#1：
3900
说明
NOIP 2006 普及组第二题

作者: 吴语林 时间: 2018-5-12 11:57

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <set>
using namespace std;
int main()
{
int f[110000]={0},v[70]={0},w[70]={0},i,w_all,n;
scanf("%d %d",&w_all,&n);
for(i=1;i<=n;i++)
{
int q;
scanf("%d %d",&w[i],&q);
v[i]=q*w[i];
}
for(i=1;i<=n;i++)
for(int j=w_all;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
printf("%d",f[w_all]);
return 0;
}

复制代码

作者: 黄煦喆 时间: 2018-5-13 21:50
以下代码仅过了5个点，请老师指点：

#include<iostream>
using namespace std;
int n,m;
int f[25][30000];
int w[25];
short v[25];
int main()
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>w[i]>>v[i];
v[i]*=w[i];
}
for(int i=1; i<=m; i++)
for(int j=n; j>=w[i]; j--)
{
f[i][j]=f[i-1][j];
f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
}
cout<<f[m][n];
return 0;
}

复制代码

作者: walk_alone 时间: 2018-5-19 19:54

#include <cstdio>
int p[26],v[26],f[26][30001];
int max(int a,int b)
{
if(a>=b)
return a;
else
return b;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&p[i],&v[i]);
for(int i=1;i<=m;i++)
for(int q=0;q<=n;q++)
{
f[i][q]=f[i-1][q];
if(q>=p[i])
f[i][q]=max(f[i-1][q],f[i-1][q-p[i]]+p[i]*v[i]);
}
printf("%d",f[m][n]);
return 0;
}

复制代码

作者: 黄煦喆 时间: 2018-5-19 22:11

黄煦喆发表于 2018-5-13 21:50
以下代码仅过了5个点，请老师指点：

AC:

#include<iostream>
using namespace std;
int n,m;
int f[25][30000];
int w[25];
int v[25];
int main()
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>w[i]>>v[i];
v[i]*=w[i];
}
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
{
f[i][j]=f[i-1][j];
if(j>=w[i])f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i][j]);
}
cout<<f[m][n];
return 0;
}

复制代码

作者: 张笑宇 时间: 2018-5-24 22:53

#include<iostream>
using namespace std;
int maxv,n,i,j;
int v[30],p[30];///v表示价格 p表示重要度
int ans;
void dfs(int x,int sumv,int sum)
{
if (sumv>maxv) return;
else if (x>=n+1) ans=max(ans,sum);
else
{
dfs(x+1,sumv,sum);
dfs(x+1,sumv+v[x],sum+v[x]*p[x]);
}
}
int main()
{
cin>>maxv>>n;
for (i=1;i<=n;i++) cin>>v[i]>>p[i];
dfs(1,0,0);
cout<<ans;
return 0;
}

复制代码

作者: admin 时间: 2018-6-3 12:07
都很好，ZXY用的dfs，HXZ和WYL用的DP，但是想想为什么HXZ第一个程序只AC了5个点？

作者: 胡雨菲菲 时间: 2018-6-5 13:47

#include <cstdio>
#include <algorithm>
using namespace std;
int n,v[30],c[30],V,f[30005];
int main()
{
scanf ("%d%d",&V,&n);
for(int i=1;i<=n;i++)
{
scanf ("%d%d",&v[i],&c[i]);
c[i]*=v[i];
}
for(int i=1;i<=n;i++)
{
for(int j=V;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+c[i]);
}
}
printf("%d",f[V]);
return 0;
}

复制代码

作者: 吴语林 时间: 2018-6-25 16:11

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <set>
using namespace std;
int main()
{
int f[110000]={0},v[70]={0},w[70]={0},i,w_all,n;
scanf("%d %d",&w_all,&n);
for(i=1;i<=n;i++)
{
int q;
scanf("%d %d",&w[i],&q);
v[i]=q*w[i];
}
for(i=1;i<=n;i++)
{
for(int j=w_all;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
printf("%d",f[w_all]);
return 0;
}

复制代码

作者: 冯文韬 时间: 2018-6-26 21:24

#include<bits/stdc++.h>
using namespace std;
int v[25],p[25],f[30005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>v[i]>>p[i];
for (int i=1;i<=m;i++)
for(int j=n;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);
cout<<f[n];
return 0;
}

复制代码

作者: 倚窗倾听风吹雨 时间: 2018-7-15 09:56

#include<iostream>
using namespace std;
int m,n,v[30],w[30],f[30][30010];
int i,j;
int main()
{
cin>>n>>m;
for(i=1;i<=m;i++)
cin>>v[i]>>w[i];
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+v[i]*w[i]);
}
}
cout<<f[m][n];
return 0;
}

复制代码

作者: zhwang 时间: 2018-7-27 20:52

#include<cstdio>
int max(int a,int b)
{
if(a>=b)
{
return a;
}
else
{
if(a<b)
{
return b;
}
}
}
int n,m;
int c[26],w[26];
int f[30001];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&c[i],&w[i]);
}
for(int i=1;i<=m;i++)
{
w[i]=c[i]*w[i];
}
for(int i=1;i<=m;i++)
{
for(int j=n;j>=c[i];j--)
{
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
}
printf("%d",f[n]);
return 0;
}

复制代码

作者: admin 时间: 2018-7-27 23:00
@ zhwang 你要注意去掉多余的大括号
@ 严梓维 if(j-v[i]>=0) 可以用循环的终止条件处理一下不需要这个判断

作者: 张笑宇 时间: 2018-7-28 10:48

#include<iostream>
using namespace std;
int maxv,n,i,j;
int v[30],p[30];///v表示价格 p表示重要度
int ans;
void dfs(int x,int sumv,int sum)
{
if (sumv>maxv) return;
else if (x>=n+1) ans=max(ans,sum);
else
{
dfs(x+1,sumv,sum);
dfs(x+1,sumv+v[x],sum+v[x]*p[x]);
}
}
int main()
{
cin>>maxv>>n;
for (i=1;i<=n;i++) cin>>v[i]>>p[i];
dfs(1,0,0);
cout<<ans;
return 0;
}

复制代码

作者: 罗笛晓 时间: 2018-10-3 16:52

#include<bits/stdc++.h>
using namespace std;
const int mm=26;
int a[mm],p[mm],v[mm];
int f[100000001];
int n,m;
int main()
{
cin>>n>>m;
f[0]=0;
for(int i=1;i<=m;i++)
{
cin>>v[i]>>p[i];
a[i]=v[i]*p[i];
}
for(int i=1;i<=m;i++)
for(int j=n;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+a[i]);
cout<<f[n];
return 0;
}

复制代码

作者: 刘至远 时间: 2018-10-5 15:33
本帖最后由刘至远于 2018-10-6 15:04 编辑

#include <bits/stdc++.h>
using namespace std;
int v[30],p[30],dp[30005];
int main()
{
ios::sync_with_stdio(0); //syn加速
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>v>>p;
dp[0]=0;
for(int i=1;i<=m;i++)
for(int j=n;j>=v;j--)
dp[j]=max(dp[j],dp[j-v]+v*p);
cout<<dp[n]<<endl;
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)