开心的金明 （C++代码）

解题思路:





注意事项:





参考代码:

/*

P1060 题解

含价值的01背包

*/

#include <cstdio>//头文件int t[1000001],m[1000001],f[1000001];//t数组是用来表示这个物品的价格（即这个物品的大小），m数组是用来表示这个物品的价值的（即这个物品的权值），f数组是用来存储答案的。int maxx(int x,int y)//maxx函数是用来判断两个数到底哪一个数大的函数{    return x>y?x:y;//如果x>y，那么就返回x，否则就返回y}int main()//主函数{    int v=0,n=0;//v表示金明的妈妈给了金明v元钱（即这个背包的大小），n表示金明有n件想买的物品（即有n件物品可以拿来放入背包）。那么，这个问题就可以简化成：有一个背包的大小为v，你可以选择将这n个物品中的几个放入这个背包里，使得这些放入背包的物品的权值最大
   scanf("%d %d",&v,&n);//输入v和n（即这个背包的容量和有n件物品可以选择放进这个背包里面）
   for(int i=1;i<=n;i++)//读入这n个物品的价格和重要度
   {        int x=0;//初始化（x是等一下要读入的第i件物品的重要度，即题目里面的p[i]）
       scanf("%d %d",&t[i],&x);//读入第i件物品的价格和它的重要度（即题目里面的v[i]和p[i]）
       m[i]=t[i]*x;//这个物品的价值（因为要求的答案是为不超过总钱数的物品的价格与重要度乘积的总和的最大值，所以将这两个数）相乘
   }    for(int i=1;i<=n;i++)//从第1件物品做到第i件物品
   {        for(int j=v-t[i];j>=0;j--)//从楼顶做到楼底
       {
           f[j+t[i]]=maxx(f[j]+m[i],f[j+t[i]]);//更新最大值（即与原来的值和新的值相比较，请想一下为什么要这样做，以及f[0]为什么不用等于1）
       }
   }    printf("%d",f[v]);//输出最大值（即答案）
   return 0;//结束程序}

评论

还没有评论

评论

作者: zhongzewei 更新时间: 2017-08-09 13:21  在Ta的博客查看  1 

其实很简单，就是个01背包

pascal代码如下：

var
   i,j,t,n,v:longint;
   f,c,w:array[0..30000]of longint;function max(a,b:longint):longint;begin
   max:=a;if b>max then max:=b;end;begin
   readln(v,n);    for i:=1 to n do readln(c[i],w[i]);//输入钱和重要度
   for i:=1 to n do
      for j:=v downto 0 do //倒着循环，不然会错
      if j-c[i] >=0 then
   f[j]:=max(f[j],f[j-c[i]]+c[i]*w[i]);
 writeln(f[v]);//输出end.

评论

还没有评论

评论

作者: Lcsy 更新时间: 2017-11-16 20:56  在Ta的博客查看  0 

这题貌似就是一个背包。。。

令f[i]表示花费i元钱能达到的最大的物品与价格的乘积的总和

所以就有 f[i]=max{f[i],f[i-v[j]]+v[i]*w[i]}

上代码

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

大概是这样了（滑稽）

评论

还没有评论

评论

作者: liyushanab 更新时间: 2017-10-22 16:38  在Ta的博客查看  0 

#include<cstdio> #include<cstring> #include<cmath> using namespace std;
int mymax(int x,int y){return x>y?x:y;}//该函数的作用是返还两数中大的那个数（如果等于就随便输出一个）。 int a[30001],b[30001],f[30001];//a数组是价格，b数组是重要度，f数组是花i元钱所能得到的最大重要度与价格的乘积。 int main() {
   int n,m;//n是总钱数，m是物品个数。
   scanf("%d%d",&n,&m);//输入n、m 。
   for(int i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]); //输入每个物品的价格和重要度。
   memset(f,0,sizeof(f));//初始化，把f数组的每一个都定义为零。
   for(int i=1;i<=m;i++)//依次比较每一个物品。
   {
       for(int j=n;j>=a[i];j--)//从大到小循环，依次询问使用这么多钱可获得的最大重要度与价格的乘积，循环到a[i]就行了。
       {
           f[j]=mymax(f[j],f[j-a[i]]+a[i]*b[i]);//判断是不买 的重要度乘价格大还是花了钱买第i个物品的重要度乘价格大（记得乘上价格，具体看题意）。
       }
   }    printf("%d\n",f[n]);//输出花n元钱所能得到的最大重要度与价格的乘积，\n是换行符，可以不打。
   return 0;
}

评论

玄学家
For the information technolory of China！

评论

作者: 孙哲远 更新时间: 2017-10-04 22:34  在Ta的博客查看  0 

其实说白了这题是dp背包中的水题，01模板一抄（当然我不建议这么做）轻松搞定（其实这些背包模板背了以后再刷几道不太一样的背包题你再遇见背包题会轻松很多。）同志们努力。For the information technolory of China！（代码呈上，详情自己看自己的书）

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