题解

202 条题解

  • 7
    @ 2017-03-15 20:31:35

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

  • 3
    @ 2017-02-26 15:36:09

    01背包。

    var
      v, p:array[1..25] of longint;
      f:array[0..30000] of qword;
      n, m, i, j:longint;
    begin
      readln(n, m);
      for i:=1 to m do readln(v[i], p[i]);
      fillchar(f, sizeof(f), 0);
      for i:=1 to m do
        for j:=n downto v[i] do if f[j-v[i]]+v[i]*p[i]>f[j] then f[j]:=f[j-v[i]]+v[i]*p[i];
      write(f[n])
    end.
    
    
  • 2
    @ 2016-10-16 16:12:38

    良心AC
    /*
    algorithm:Zero_One_Pack
    written by wx
    time:2016/10/16 4:05
    /
    #include <stdio.h>
    using namespace std;
    int max(int a,int b)
    {
    if(a>b)return a;
    return b;
    }
    int main()
    {
    int n,v,cost[30],g[30],i,j,f[30001]={};
    scanf("%d%d",&v,&n);
    for(i=1;i<=n;i++)
    {
    scanf("%d%d",&cost[i],&g[i]);
    g[i]
    =cost[i];
    }
    for(i=1;i<=n;i++)
    {
    for(j=v;j>=cost[i];j--)
    f[j]=max(f[j],f[j-cost[i]]+g[i]);
    }
    printf("%d",f[v]);
    return 0;
    }

  • 1
    @ 2020-08-29 11:21:40

    必过
    #include<bits/stdc++.h>
    using namespace std;
    long long w[10001],v[10001],a[802003],n,m;
    int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    cin>>w[i]>>v[i];
    }
    for(int i=1;i<=m;i++){
    for(int j=n;j>=w[i];j--){
    a[j]=max(a[j],a[j-w[i]]+v[i]*w[i]);
    }
    }
    cout<<a[n];
    return 0;
    }

  • 1
    @ 2020-05-15 22:52:50

    背包问题主要是背模板,这里收录了一些模板

    一些复杂的背包问题(如泛化物品)未收录

    01背包问题:

    无优化

    for(int i=1;i<=n;i++)
    {
        for(int c=0;c<=m;c++)
        {
            f[i][c]=f[i-1][c];
            if(c>=w[i])
            f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
        }
    }
    

    一维数组优化:

    for(int i=1;i<=n;i++)
    {
        for(int c=m;c>=0;c--)
        {
            if(c>=w[i])
            f[c]=max(f[c],f[c-w[i]]+v[i]);
        }
    }
    

    更进一步的常数优化:

    for(int i=1;i<=n;i++)
    {
        sumw+=w[i];
        bound=max(m-sumw,w[i]);
        for(int c=m;c>=bound;c--)
        {
            if(c>=w[i])
            f[c]=max(f[c],f[c-w[i]]+v[i]);
        }
    }
    

    完全背包问题:

    for(int i=1;i<=n;i++)
    {
        for(int c=0;c<=m;c++)
        {
            if(c>=w[i])
            f[c]=max(f[c],f[c-w[i]]+v[i]);
        }
    }
    

    多重背包问题:

    for(int i=1;i<=n;i++)
    {
        if(w[i]*a[i]>m)
        {
            for(int c=0;c<=m;c++)
            {
            if(c>=w[i])
            f[c]=max(f[c],f[c-w[i]]+v[i]);
            }
        }
        else
        {
             k=1;amount=a[i];
             while(k<amount)
             {
                 for(int c=k*w[i];c>=0;c--)
                 {
                     if(c>=w[i])
                     f[c]=max(f[c],f[c-w[i]]+k*v[i]);
                 }
                 amount-=k;
                 k<<=1;
             }  
             for(int c=amount*w[i];c>=0;c--)
             {
                 f[c]=max(f[c],f[c-w[i]]+amount*v[i]);
             }
        } 
    }
    

    下面来到我们的正题: 首先判断是否为背包问题,可见其背包就是money的总数,质量就是重要度*money

    可以套用背包问题

    有根据其特性可知这是01背包

    到此建模完成,思考+读题用时3min

    #include<iostream> 
    #include<cstdio> 
    using namespace std; 
    int main(){ 
        int n,m,i,j,v,im,dp[30003]={0}; 
        scanf("%d%d",&n,&m); 
        for(i=1;i<=m;i++){ 
          scanf("%d%d",&v,&im); 
          for(j=n;j>=v;j--){ 
            dp[j]=max(dp[j-v]+v*im,dp[j]); 
          }} 
        printf("%d",dp[n]); 
        return 0;} 
    
    

    求赞

  • 1
    @ 2017-11-25 18:29:38

    裸的01背包...

    #include<bits/stdc++.h>
    using namespace std;
    int a[26],f[30001],x[26];
    int main(){
        int n,m;
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&x[i]);
        for(int i=1;i<=n;i++)
            for(int j=m;j>=a[i];j--)
                f[j]=max(f[j],f[j-a[i]]+a[i]*x[i]);
        printf("%d",f[m]);
        return 0;
    }
    
  • 1
    @ 2017-10-28 19:21:20

    //题目中价值和重要度乘起来,就相当于01背包中de价值;
    //题目中的价值相当于01背包的重量,然后这就是一个模板题;
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int wr[26][30000];
    int im[26];
    int zi[26];
    int v[26];
    int main()
    {int mem,n;
    cin>>mem>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>v[i]>>im[i];
    }
    memset(wr,0,sizeof(wr));
    for(int i=1;i<=n;i++)
    zi[i]=v[i]*im[i];
    for(int i=1;i<=n;i++)
    {
    for(int j=mem;j>=0;j--)
    {if(j>=v[i])wr[i][j]=max(wr[i-1][j-v[i]]+zi[i],wr[i-1][j]);
    else wr[i][j]=wr[i-1][j];
    }
    }

    cout<<wr[n][mem];

    return 0;
    }

  • 0
    @ 2021-02-25 15:45:15
    #include <bits/stdc++.h>
    using namespace std;
    int dp[1000011], v[1000010], w[1000011], num[1000011], s = 0, p, k, l, n, m;
    int main() {
        cin >> n>>m;
        for (int i = 1; i <= m; i++) cin >> v[i] >> w[i];
        for (int i = 1; i <= m; i++)
            for (int j = n; j >= v[i]; j--) dp[j] = max(dp[j], dp[j - v[i]] + w[i]*v[i]);
        cout << dp[n];
        return 0;
    }
    
  • 0
    @ 2020-07-17 22:52:21

    dp万岁!!!

    #include<bits/stdc++.h>
    using namespace std;
    int t,n,dp[30020],a[20020],b[20020];
    int main()
    {
        memset(dp,0,sizeof(dp));
        cin>>t>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i]>>b[i],b[i]*=a[i];
        for(int i=1;i<=n;i++)
        {
            for(int j=t;j>=a[i];j--)
                dp[j]=max(dp[j-a[i]]+b[i],dp[j]);
        }
        cout<<dp[t]<<endl;
        return 0;
    }
    
  • 0
    @ 2018-01-03 14:48:05
    #include<cstdio>
    #include<iostream>
    int dp[1000001];
    int w[1000001], val[1000001];
    int main() {
        int t, m;
        scanf("%d%d", &t, &m);
        for(int i=1; i<=m; i++) {
            int x;
            scanf("%d%d", &w[i], &x);
            val[i]=w[i]*x;
        }
        for(int i=1; i<=m; i++)
            for(int j=t-w[i]; j>=0; j--)
                dp[j+w[i]]=std::max(dp[j]+val[i], dp[j+w[i]]);
        printf("%d", dp[t]);
        return 0;
    }
    
  • 0
    @ 2017-11-03 09:40:41

    典型的01背包
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,val,like;
    int f[30001];

    int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
    scanf("%d%d",&val,&like);
    for(int j=n;j>=val;--j){
    f[j]=max(f[j],f[j-val]+val*like);
    }
    }
    printf("%d",f[n]);
    return 0;
    }

  • 0
    @ 2017-10-28 11:06:26

    #include <iostream>

    /* run this program using the console pauser or add your own getch, system("pause") or input loop /
    using namespace std;
    int s[30][300010]={}; //定义一个存储数组
    int main(int argc, char
    * argv)
    {
    int m,n,a[30]={0},b[30]={0},i,j;
    cin>>m>>n;
    for(i=1;i<=n;i++)
    {
    cin>>a[i]>>b[i]; //循环输入价格数组a[i]和重要成度数组b[i]
    }
    for(i=1;i<=n;i++)
    {
    for(j=0;j<=m;j++) //双重循环 循环 1~1000(输入实例)
    {
    if(j>=a[i]) //如果j大于a[i](商品价格)
    s[i][j]=max(s[i-1][j],s[i-1][j-a[i]]+a[i]*b[i]); //比较【下一件商品】和【下一件商品的1~1000-物品价格】(max是指比较两个中最大的那个数,地球人都知道,哈哈)
    else
    s[i][j]=s[i-1][j]; //否则,把下一件商品赋值给s[i][j];
    }
    }
    cout<<s[n][m-1]; //输出结果
    return 0;
    }

  • 0
    @ 2017-10-13 21:56:23

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

  • 0
    @ 2017-03-15 20:31:21

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

  • 0
    @ 2016-09-05 13:16:11
    #include<cstdio>
    using namespace std;
    long long n,m,v[1000001],p[1000001],f[1000001];
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)scanf("%d%d",&v[i],&p[i]);
        for(int i=1;i<=m;i++)
        {
            for(int j=n;j>=v[i];j--)
            {
                if(f[j-v[i]]+v[i]*p[i]>f[j])f[j]=f[j-v[i]]+v[i]*p[i];
            }
        }
        printf("%d\n",f[n]);
    }
    
  • 0
    @ 2016-09-05 13:14:56

    #include<cstdio>
    using namespace std;
    long long n,m,v[1000001],p[1000001],f[1000001];
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&v[i],&p[i]);
    for(int i=1;i<=m;i++)
    {
    for(int j=n;j>=v[i];j--)
    {
    if(f[j-v[i]]+v[i]*p[i]>f[j])f[j]=f[j-v[i]]+v[i]*p[i];
    }
    }
    printf("%d\n",f[n]);
    }

  • 0
    @ 2016-08-23 13:59:30
    var 
        n,m,i,j:longint;
        a,b:array[1..1000000] of qword;
        f:array[-30..1000000] of qword;
    begin
        readln(n,m);
        for i:=1 to m do readln(a[i],b[i]);
        for i:=1 to m do
            for j:=n downto a[i] do 
                if f[j-a[i]]+a[i]*b[i]>f[j] 
                    then f[j]:=f[j-a[i]]+a[i]*b[i];
        writeln(f[n]);
    end.
    
  • 0
    @ 2016-08-04 10:48:19

    var m,n,i,j:longint;
    k,v:array[1..25] of longint;
    f:array[0..1000000] of longint;
    begin
    readln(m,n);
    for i:=1 to n do
    readln(k[i],v[i]);
    for i:=1 to n do
    for j:=m downto k[i] do
    if f[j-k[i]]+k[i]*v[i]>f[j] then
    f[j]:=f[j-k[i]]+k[i]*v[i];
    writeln(f[m]);
    end.

  • 0
    @ 2016-07-15 16:02:26

    暴搜略剪枝

    #include <iostream>
    using namespace std;
    int t=0,w[1000],v[1000], c,k;
    void bs(int bj, int p,int c)
    {
    if(c<=0)
    return;
    if(bj>k){

    t=max(t,p);
    return;
    }
    else{
    bs(bj+1,p+w[bj],c-v[bj]);
    bs(bj+1,p,c);

    }
    }
    int main()
    {
    cin>>c>>k;
    int i;
    for(i=1;i<=k;i++){
    cin>>v[i]>>w[i];
    w[i]=w[i]*v[i];
    }
    bs(1,0,c);
    cout<<t;
    return 0;
    }

  • 0
    @ 2016-07-15 15:10:21

    #include <iostream>
    #include <math.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    int n,m,v[30],p[30],f[30005];
    int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i ++)scanf("%d%d",&v[i],&p[i]);
    for(int i = 1;i <= m;i ++){
    for(int j = n;j >=0;j --){
    f[j] = j >= v[i] ? max(f[j - v[i]] + p[i] * v[i],f[j]) : f[j];
    }
    }
    printf("%d",f[n]);

    return 0;
    }

信息

ID
1317
难度
3
分类
动态规划 | 背包 点击显示
标签
递交数
6525
已通过
3295
通过率
50%
被复制
17
上传者