/ Vijos / 题库 / 采药 /

题解

288 条题解

  • 8
    @ 2017-04-24 13:13:26
    /*
    作者:larryzhong
    题目:p1102 采药
    */
    
    #include <iostream>
    using namespace std;
    
    const int maxn = 1010, maxv = 5010;
    long long c[maxn], w[maxn], f[maxn][maxv];
    
    int main() {
        int V, n;
        cin >> V >> n;
        for (int i = 1; i <= n; i++)
            cin >> c[i] >> w[i];
        for (int i = 1; i <= n; i++)
            for (int v = 0; v <= V; v++) {
                if (v >= c[i])
                    f[i][v] = max(f[i - 1][v], f[i - 1][v - c[i]] + w[i]);
                else
                    f[i][v] = f[i - 1][v];
            }
        cout << f[n][V] << endl;
        return 0;
    }
    
  • 3
    @ 2018-04-20 13:09:22

    #include<iostream>
    using namespace std;
    typedef long long ll;
    const int maxx=6666;
    int main()
    {
    ll f[maxx],w[maxx],v[maxx],n,t;
    cin>>t>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
    for(int j=t;j>=w[i];j--)
    {
    f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
    cout<<f[t];
    return 0;
    }

  • 2
    @ 2019-01-19 14:38:29

    现在这么流行DP吗?
    我特别喜欢写DFS,不过是个编程的人都知道暴力是不可以过的。
    所以我加了最优性剪枝(启发式搜索)
    详见代码

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N = 105 ;
    int n,m,ans;
    struct Node{
        int a,b;//a代表时间,b代表价值 
        double f;//性价比 
    }node[N];
    bool cmp(Node p,Node q) {
        return p.f>q.f;//按性价比排序 
    }
    int f(int t,int v){//估值函数 
        int tot=0;
        for(int i=1;t+i<=n;i++)
            if(v>=node[t+i].a){
                v-=node[t+i].a;
                tot+=node[t+i].b;
            }
            else 
                return (int)(tot+v*node[t+i].f);
        return tot;
    }
    void dfs(int t,int p,int v){
        ans=max(ans,v);
        if(t>n) return ;
        if(f(t,p)+v>ans) dfs(t+1,p,v);//判断,如果后面的药品达不到ans就不搜索了 
        if(node[t].a<=p) dfs(t+1,p-node[t].a,v+node[t].b);
    }
    int main(){
        scanf("%d %d",&m,&n);//读入大小和 
        for(int i=1;i<=n;i++){
            scanf("%d %d",&node[i].a,&node[i].b);
            node[i].f=1.0*node[i].b/node[i].a;//计算性价比
        }
        sort(node+1,node+n+1,cmp);//按性价比排序 
        dfs(1,m,0);
        printf("%d\n",ans);
        return 0;
    }
    
  • 2
    @ 2017-10-03 19:25:11

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int w[1005];
    int k[1005];
    int f[1005]; //一维优化
    int main()
    {
    int n,s;
    scanf("%d",&s);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d",&w[i],&k[i]);
    }
    for(int i=1;i<=n;i++)
    {
    for(int j=s;j>=w[i];j--)
    {
    f[j]=max(f[j-w[i]]+k[i],f[j]);
    }
    }
    printf("%d",f[s]);
    return 0;
    }

  • 2
    @ 2017-10-03 14:48:30

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    long long t[110],m[110],f[1010][1010];
    int main()
    {
    int a,n;//a表示总时间,n表示山洞里草药的数目
    cin>>a>>n;
    for(int i=1;i<=n;i++)
    cin>>t[i]>>m[i];//循环输入每种草药采摘所需的时间和价值
    for(int i=1;i<=n;i++)
    for(int j=0;j<=a;j++)
    {
    if(j>=t[i])//如果总时间大于采药所需时间
    f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+m[i]);
    else f[i][j]=f[i-1][j];
    //对比不采当前草药能获得的最大价值和采当前草药能获得的最大价值
    }
    cout<<f[n][a]<<endl;//输出最大价值
    return 0;
    }

  • 2
    @ 2017-10-03 14:43:38

    c++ 啦啦啦啦啦啦

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    long long t[110],m[110],f[1010][1010];
    int main()
    {
    int a,n;//a表示总时间,n表示山洞里草药的数目
    cin>>a>>n;
    for(int i=1;i<=n;i++)
    cin>>t[i]>>m[i];//循环输入每种草药采摘所需的时间和价值
    for(int i=1;i<=n;i++)
    for(int j=0;j<=a;j++)
    {
    if(j>=t[i])//如果总时间大于采药所需时间
    f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+m[i]);
    else f[i][j]=f[i-1][j];
    }
    cout<<f[n][a]<<endl;
    return 0;
    }

  • 2
    @ 2017-10-03 14:31:48

    啦啦啦啦啦啦

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    long long c[1010],w[1010],f[1010][1010];
    int main()
    {
    int V,n;
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    cin>>c[i]>>w[i];
    for(int i=1;i<=n;i++)
    for(int j=0;j<=V;j++)
    {
    if(j>=c[i])
    f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
    else f[i][j]=f[i-1][j];
    }
    cout<<f[n][V]<<endl;
    return 0;
    }

  • 1
    @ 2019-08-22 20:46:27

    \(01\)背包模板。 我第一次发题解,大家多多照顾

    很显然本题的数据范围是\(n \leq 30\),完全可以用\(dfs+\)一些剪枝写过去。

    但是,如果\(n,V \leq 1000\),那么就只能\(dp\).

    用\(dp[i][j]\)表示用\(j\)的容量选择前\(i\)个物品可以获得的最大价值。

    那么,我们需要考虑第\(i\)个物品。

    dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

    前者:不选当前的。

    后者:选当前的,背包容量缩小,加上当前的价值。

    然而数组下标显然非负,所以要保证\(j \geq v_i\),否则就只能选择dp[i-1][j]

    二维数组的好处是:**不用考虑循环的正反问题。**

    显然可以弄成一维(滚动数组),但是没必要,那样还要研究循环的正反,太麻烦。(当然除非真的有内存的压缩需求)

    献上本巨佬的代码。

    #include<bits/stdc++.h>
    using namespace std;
    
    int V,n;
    int dp[1001][1001];
    int v[1001],w[1001];
    
    inline int read(){char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();
        int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x;}
    
    int main(){
        V=read(),n=read();
        for(int i=1;i<=n;i++) v[i]=read(),w[i]=read();
        for(int i=1;i<=n;i++)
        for(int j=1;j<=V;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
        printf("%d\n",dp[n][V]);
        return 0;
    }
    
    
  • 1
    @ 2019-05-15 20:16:42

    f是动态规划数组。
    x为时间,y为价值。
    二维时由上一层推来,状态转移方程:
    f[i,j]:=max(f[i,j],f[i-1,j-x]+y);
    而现在改成了一维,状态要倒着放,
    否则当前一层前面的状态会影响目前的操作。
    状态转移方程:
    f[i]:=f[i-x]+y;
    这绝对是最简单的动规写法......
    Pascal程序:
    var n,m,i,j,x,y,max:longint;
    f:array[0..1001] of longint;
    begin
    readln(m,n);
    for i:=1 to n do
    begin
    readln(x,y);
    for j:=m downto x do
    if f[j-x]+y>f[j] then
    f[j]:=f[j-x]+y;
    end;
    for i:=1 to m do
    if f[i]>max then
    max:=f[i];
    writeln(max);
    end.

  • 1
    @ 2018-10-24 15:56:05
    //来一份记忆化搜索
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define For(i,l,r) for(int i=l;i<=r;i++)
    #define N 1005
    using namespace std;
    
    int n,m,f[N][N],val[N],w[N];
    int dfs(int i,int v){
        if (f[i][v]!=-1) return f[i][v];
        if (i==0 || v<=0) return 0;
        if (w[i]>v) f[i][v]=dfs(i-1,v);
        else f[i][v]=max(dfs(i-1,v),dfs(i-1,v-w[i])+val[i]);
        return f[i][v];
    }
    int main(){
        memset(f,-1,sizeof(f));
        scanf("%d%d",&m,&n);
        For(i,1,n){
            scanf("%d%d",&w[i],&val[i]);
        }
        printf("%d\n",dfs(n,m));
        return 0;
    }
    
  • 1
    @ 2018-04-05 13:56:05

    水题,pascal代码见下

    program noname01;
    var t,m:integer;
      c:array[1..100] of integer;
      w:array[1..100] of integer;
      f:array[1..1000] of integer;
      i,ans:integer;
     procedure zo(cost:integer;weight:integer);
     var v:integer;
     begin
       for v:=t downto cost do
       if f[v-cost]+weight>f[v] then f[v]:=f[v-cost]+weight;
     end;
     begin
     for i:=1 to 1000 do f[i]:=0;
     ans:=0;
      read(t,m);
     for i:=1 to m do
       read(c[i],w[i]);
     for i:= 1 to m do
       zo(c[i],w[i]);
     for i:=1 to t do
       if f[i]>ans then ans:=f[i];
     write(ans);
     end.
    
  • 1
    @ 2018-02-06 22:30:49
    #include <iostream>
    #include <cmath>
    #include <cstring>
    using namespace std;
    int dp[1000][1000],t[1000],v[1000];
    int main(){
        int time_max,item_max,item,time=0;
        memset(dp,0,sizeof(dp));
        memset(t,0,sizeof(t));
        memset(v,0,sizeof(v)); 
        cin>>time_max>>item_max;
        for(item=1;item<=item_max;item++)
            cin>>t[item]>>v[item];
        for(item=1;item<=item_max;item++){
            for(time=time_max;time>=t[item];time--)
                dp[item][time]=max(dp[item-1][time-t[item]]+v[item],dp[item-1][time]);
            for(time=t[item]-1;time>=0;time--)
                dp[item][time]=dp[item-1][time];
        }
        cout<<dp[item_max][time_max]<<endl;
    }
    
  • 1
    @ 2018-01-29 18:12:02

    典型的01背包问题,用一维数组解决,不需要存数据

    import java.util.Scanner;

    public class Main {
    static Scanner in = new Scanner(System.in);
    static int n, m;
    static int[] dp = new int[105];
    public static void main(String[] args) {
    n = in.nextInt();
    m = in.nextInt();
    for (int i = 1; i <= m; i++) {
    int a = in.nextInt();
    int b= in.nextInt();
    for (int j = n; j >= 0; j--) {
    if (j >= a) {
    dp[j] = Math.max(dp[j], dp[j - a] + b);
    }
    }
    }
    System.out.println(dp[n]);
    }

    }

  • 1
    @ 2018-01-03 14:50:22
    #include<cstdio>
    #include<iostream>
    int dp[1010];
    int w[110], val[110];
    int main(){
        int t, m;
        scanf("%d%d", &t, &m);
        for(int i=1; i<=m; i++) scanf("%d%d", &w[i], &val[i]);
        for(int i=1; i<=m; i++)
            for(int j=t; j>=0; j--)
                if(j>=w[i]) dp[j]=std::max(dp[j-w[i]]+val[i], dp[j]);
        printf("%d", dp[t]);
        return 0;
    }
    
  • 1
    @ 2017-10-31 18:08:34

    第一道DP题,开心(= ̄ω ̄=)

    #include<iostream>
    using namespace std;
    int h[110],w[110],dp[110][110];
    int main()
    {
        int t,m;
        cin>>t>>m;
        for(int i=1;i<=m;++i)
        cin>>h[i]>>w[i];
        for(int i=1;i<=m;++i)
        {
            for(int j=t;j>=0;j--)
            {
                if(j>=h[i])
                dp[i][j]=max(dp[i-1][j-h[i]]+w[i],dp[i-1][j]);
                else
                dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[m][t];
        return 0;
    }
    
  • 0
    @ 2018-11-04 11:07:11

    Pascal代码
    var
    i,j,x,y,t,m:longint;
    f:array[0..1000] of longint;
    begin
    readln(t,m);
    for i:=1 to m do
    begin
    readln(x,y);
    for j:=t downto x do
    if f[j-x]+y>f[j] then f[j]:=f[j-x]+y;
    end;
    write(f[t]);
    end.

  • 0
    @ 2018-08-11 15:29:12
    #include <stdio.h>
    
    /*背包问题:f[i][j]代表在前i个时间单位内,考虑前j株草药,所能得到的最大价值。*/
    
    int f[1001][101];
    
    int cost[101];
    int value[101];
    
    int t, m;
    
    int max_val(int a, int b) {
        return a < b ? b : a;
    }
    
    int main()
    {
        int i, j;
        scanf("%d%d", &t, &m);
        for (i = 1; i <= m; i++) {
            scanf("%d%d", cost + i, value + i);
        }
        for (i = 1; i <= t; i++) {
            for (j = 1; j <= m; j++) {
                f[i][j] = f[i][j-1];
                if (i >= cost[j]) {
                    f[i][j] = max_val(f[i][j], f[i - cost[j]][j-1] + value[j]);
                }
            }
        }
        printf("%d", f[t][m]);
        return 0;
    }
    
    
  • 0
    @ 2017-11-06 16:30:30

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    long long t,m,a[1001],b[1001],f[100001];
    int main()
    {
    cin>>t>>m;
    for(int i=1;i<=m;i++)
    cin>>a[i]>>b[i];
    for(int i=1;i<=m;i++)
    for(int j=t;j>=a[i];j--)
    f[j]=max(f[j],f[j-a[i]]+b[i]);
    cout<<f[t];
    return 0;
    }

  • 0
    @ 2017-11-06 13:12:34

    这道题的数据范围比较弱,所以二维背包也可以跑过,理解二维背包主要是要理解第一和第二个中括号代表的东西,于是就很好解开了。
    #include <bits/stdc++.h>
    using namespace std;
    int at,n;
    int t[1005],m[1005];
    int f[1005][1005];
    int maxx(int x,int y){
    if (x>y)return x;
    else return y;
    }
    int main(){
    scanf ("%d%d",&at,&n);
    for (int i=1;i<=n;i++)scanf ("%d%d",&t[i],&m[i]);
    for (int i=1;i<=at;i++)
    for (int j=at;j>0;j--){
    if (t[i]<=j)
    f[i][j]=maxx(f[i-1][j],f[i-1][j-t[i]]+m[i]);//这里第一个代表选的药数;
    else f[i][j]=f[i-1][j];//第二个代表剩余时间。
    }
    printf ("%d",f[n][at]);
    return 0;
    }

  • 0
    @ 2017-10-17 17:17:20

    var
    t,m,i,j,maxn:longint;
    f:array[0..10000] of longint;
    a,w:array[1..10000] of longint;
    begin
    readln(T,M);
    for i:=1 to m do readln(a[i],w[i]);
    f[0]:=0;
    for i:=1 to m do
    for j:=t downto 0 do
    begin
    if j>=a[i] then
    f[j]:=max(f[j],f[j-a[i]]+w[i])
    else f[j]:=f[j];
    end;
    maxn:=-maxlongint;
    for j:=1 to t do
    begin
    if f[j]>maxn then maxn:=f[j];
    end;
    writeln(maxn);
    end.

信息

ID
1104
难度
4
分类
动态规划 | 背包 点击显示
标签
递交数
16091
已通过
6250
通过率
39%
被复制
7
上传者