题解

203 条题解

  • 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;
    }

  • 0
    @ 2016-07-12 23:01:37

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1344 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 1344 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 1340 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 1336 KiB, score = 10
    Accepted, time = 15 ms, mem = 1344 KiB, score = 100

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    long long n,m,w[30],c[30],dp[100000];
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>w[i]>>c[i];
    for(int i=1;i<=m;i++)
    {
    for(int j=n;j>=w[i];j--)
    {
    dp[j]=max(dp[j],dp[j-w[i]]+c[i]*w[i]);
    }
    }
    cout<<dp[n]<<endl;
    return 0;
    }

    Accepted like a cork.

  • 0
    @ 2016-06-10 18:17:00

    转化成01背包问题
    递推 滚动数组
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int d[30000+3];
    int main(){
    int n,m;
    cin>>n>>m;
    memset(d,0,sizeof(d));
    int v,w;
    for(int i=1;i<=m;i++){
    scanf("%d%d",&v,&w);w=v*w;
    for(int j=n;j>=0;j--){
    if(j>=v) d[j]=max(d[j],d[j-v]+w);

    }
    }
    cout<<d[n];
    return 0;
    }

  • 0
    @ 2016-05-31 19:47:56

    #include <iostream>
    using namespace std;
    const int MAXM=30;
    const int MAXV=30010;
    int dp[MAXM][MAXV];
    int vi[MAXM],pi[MAXM];
    int main()
    {
    int m,v;
    cin>>v>>m;
    for(int i=1;i<=m;i++)
    {
    cin>>vi[i]>>pi[i];
    pi[i]*=vi[i];
    }
    for(int i=1;i<=m;i++)
    for(int j=0;j<=v;j++)
    {
    if(j<vi[i])
    dp[i][j]=dp[i-1][j];
    else
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi[i]]+pi[i]);
    }
    cout<<dp[m][v]<<endl;
    return 0;

    }

  • 0
    @ 2016-05-24 18:22:43

    #include <cstdio>
    #include <iostream>
    using std::max;

    int main(void){
    freopen("in.txt","r",stdin);
    int n,maxm;
    int c[30],w[30];
    int f[30020]={0};
    scanf("%d%d",&maxm,&n);
    for(int i=1;i<=n;i++){
    scanf("%d%d",&c[i],&w[i]);
    w[i]*=c[i];
    }
    for(int i=1;i<=n;i++)\
    for(int j=maxm;j>=c[i];j--)
    f[j]=max(f[j-c[i]]+w[i],f[j]);
    printf("%d",f[maxm]);
    return 0;
    }

  • 0
    @ 2015-12-14 21:17:08

    #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;
    }

  • 0
    @ 2015-12-14 21:15:55

    #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[30][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[i][j] = j >= v[i] ? max(f[i -1][j - v[i]] + p[i] * v[i],f[i - 1][j]) : f[i - 1][j];
    }
    }
    printf("%d",f[m][n]);

    return 0;
    }

  • 0
    @ 2015-10-22 15:06:33

    #include <cstdio>

    using namespace std;

    inline int max(int a,int b) {
    return a>b?a:b;
    }

    int main(void) {
    int n=0,v=0;
    scanf("%d %d",&v,&n);
    int w[n],c[n];
    for (int i=0;i<n;++i) {
    int temp=0;
    scanf("%d %d",c+i,&temp);
    w[i]=temp*c[i];
    }
    int f[v+1];
    for (int i=0;i<=v;++i)
    f[i]=0;
    for (int i=0;i<n;++i)
    for (int j=v;j>=0;--j)
    if (j>=c[i])
    f[j]=max(f[j],f[j-c[i]]+w[i]);
    int ans=0;
    for (int i=0;i<v+1;++i)
    if (f[i]>ans)
    ans=f[i];
    printf("%d\n",ans);
    return 0;
    }
    QwQ我好菜

  • 0
    @ 2015-10-11 20:11:48

    评测状态 Accepted
    题目 P1317 开心的金明
    递交时间 2015-10-09 17:29:42
    代码语言 Pascal
    评测机 VijosEx
    消耗时间 177 ms
    消耗内存 24248 KiB
    评测时间 2015-10-09 17:29:43
    评测结果
    编译成功

    Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
    Copyright (c) 1993-2014 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    foo.pas(12,32) Warning: Variable "f" does not seem to be initialized
    Linking foo.exe
    13 lines compiled, 0.1 sec , 29824 bytes code, 1628 bytes data
    1 warning(s) issued
    测试数据 #0: Accepted, time = 6 ms, mem = 24248 KiB, score = 10
    测试数据 #1: Accepted, time = 19 ms, mem = 24248 KiB, score = 10
    测试数据 #2: Accepted, time = 20 ms, mem = 24248 KiB, score = 10
    测试数据 #3: Accepted, time = 20 ms, mem = 24248 KiB, score = 10
    测试数据 #4: Accepted, time = 31 ms, mem = 24248 KiB, score = 10
    测试数据 #5: Accepted, time = 3 ms, mem = 24248 KiB, score = 10
    测试数据 #6: Accepted, time = 16 ms, mem = 24248 KiB, score = 10
    测试数据 #7: Accepted, time = 16 ms, mem = 24244 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 24248 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 24248 KiB, score = 10
    Accepted, time = 177 ms, mem = 24248 KiB, score = 100
    代码
    var n,m,i,j:longint;
    w,v,f:array[-1..1000000]of int64;
    function max(x,y:int64):int64;
    begin
    if x>y then max:=x else max:=y;
    end;
    begin
    readln(m,n);
    for i:=1 to n do readln(w[i],v[i]);
    for i:=1 to n do
    for j:=m downto 1 do
    if j>=w[i] then f[j]:=max(f[j],f[j-w[i]]+w[i]*v[i]);
    writeln(f[m]);
    end.

    呵呵,第六遍…………………………………………………………………………………………………………………………,终于过了,太煎熬了,各位注意很容易就超时
    !!!!!!!被坑了好几次!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

  • 0
    @ 2015-08-23 16:07:17

    #include <iostream>
    #include <cstdio>

    using namespace std;
    int f[30][30005],i,j,k,n,m,l,v[30],w[30];
    int main()
    {
    cin >>n>>m;
    for (i=1;i<=m;i++)
    cin >>v[i]>>w[i];
    for (i=1;i<=m;i++)
    for (j=0;j<=n;j++)
    if (j>v[i])
    {
    f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*w[i]);
    }
    else f[i][j]=f[i-1][j];
    cout <<f[m][n];
    }

  • 0
    @ 2015-07-09 10:03:41

    var n,m,i,j:longint;
    v,p:array[1..25] of longint;
    a:array[0..25,0..30000] of longint;
    function max(b,c:longint):longint;
    begin
    if b>c then exit(b) else exit(c)
    end;
    begin
    read(m,n);
    for i:=1 to n do
    read(v[i],p[i]);
    for i:=1 to n do
    for j:=1 to m do
    if j>=v[i] then a[i,j]:=max(a[i-1,j],a[i-1,j-v[i]]+v[i]*p[i])
    else a[i,j]:=a[i-1,j];

    write(a[n,m])
    end.

  • 0
    @ 2015-06-19 09:30:29

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <string>
    #include <algorithm>

    using namespace std;

    const int MAXN = 30010;
    const int MAXM = 32;

    int bp[MAXM][MAXN], v[MAXM], w[MAXM];

    int main()
    {
    #ifdef OFFLINE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    memset(bp, 0, sizeof(bp));
    memset(v, 0, sizeof(v));
    memset(w, 0, sizeof(w));

    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++)
    scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
    if (v[i] <= j)
    bp[i][j] = max(bp[i - 1][j], bp[i - 1][j - v[i]] + v[i] * w[i]);
    else
    bp[i][j] = bp[i - 1][j];

    int maxnum = 0;
    for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
    maxnum = max(maxnum, bp[i][j]);

    printf("%d\n", maxnum);

    return 0;
    }

  • 0
    @ 2015-05-13 18:24:34

    测试数据 #0: Accepted, time = 0 ms, mem = 364 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 368 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 368 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 368 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 364 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 368 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 364 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 368 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 368 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 368 KiB, score = 10
    Accepted, time = 15 ms, mem = 368 KiB, score = 100
    代码
    #include <iostream>
    #include <cstring>

    #define MAX(A,B) A>B?A:B

    using namespace std;

    struct Item{
    int itemPrice;
    int itemValue;
    };

    int main(){
    int totalMoney,itemNum;
    int value[30001];
    memset(value, 0, 30001*sizeof(int));
    Item item[26];
    cin >> totalMoney >> itemNum;
    for(int i = 1; i <= itemNum; i++)
    cin >> item[i].itemPrice >> item[i].itemValue;
    for(int i = 1; i <= itemNum; i++){
    for(int j = totalMoney; j >= 0; j--){
    if(j >= item[i].itemPrice) value[j] = MAX(value[j], value[j - item[i].itemPrice] + item[i].itemPrice * item[i].itemValue);
    }
    }
    cout << value[totalMoney] << endl;
    }

  • 0
    @ 2015-03-18 09:55:27

    #include<stdio.h>
    #include<string.h>
    int v[10000],p[10000],d[26][30001];
    int main()
    {
    int i,j,k,n,m;
    scanf("%d%d",&n,&m);
    int w[m+1];
    for(i=0;i<m;i++)w[i]=0;
    //memset(w,0,sizeof(w));
    for(i=0;i<m;i++)
    {
    scanf("%d%d",&v[i],&p[i]);
    w[i]=v[i]*p[i];
    }
    //memset(d,0,sizeof(d));
    for(i=m-1;i>=0;i--)
    {
    for(j=0;j<=n;j++)
    {
    d[i][j]=(i==m-1?0:d[i+1][j]);
    if(j>=v[i])d[i][j]=d[i][j]>d[i+1][j-v[i]]+w[i]?d[i][j]:d[i+1][j-v[i]]+w[i];
    }
    }
    printf("%d",d[0][n]);
    return 0;
    }
    逆推的顺序

  • 0
    @ 2015-01-18 12:06:14

    #include <iostream>
    #include <algorithm>
    using namespace std;

    int dp[26][30001], w[MAXL], p[MAXL];

    int main()
    {
    int V, n;
    cin >> V >> n;
    for (int i = 1; i <= n; i++)
    {
    cin >> w[i] >> p[i];
    p[i] *= w[i];
    }

    for (int i = 1; i <= n; i++)
    {
    for (int j = V; j > 0; j--)
    {
    if (j >= w[i])
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
    else
    dp[i][j] = dp[i - 1][j];
    }
    }
    cout << dp[n][V] << endl;
    }

  • 0
    @ 2015-01-18 11:18:59

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int i,j,p[30],v[30],n,m,f[30010];
    int main()
    {
    cin>>n>>m;
    for(i=1;i<=m;i++)
    cin>>v[i]>>p[i];
    for(i=1;i<=m;i++)
    for(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];
    for(i=1;i<=n;i++)
    if(f[i]>f[0])
    f[0]=f[i];
    cout<<f[0];
    return 0;
    }

  • 0
    @ 2015-01-14 20:20:57

    这是一道01背包问题,只不过稍稍做了改动,即把价值藏了起来,变为重要度和价格乘积罢了。总钱就是容量,价格是体积。不是难题。

    推荐和小飞侠的游园方案和采药一起写,这样刚好练习巩固01背包,因为01背包最基础也最重要。

    ###block code
    program P1317;
    uses math;
    var data:array[0..30000] of longint;
    n,m,v,p,sum,i,j:longint;
    begin
    fillchar(data,sizeof(data),0); read(n,m);
    for i:=1 to m do //直接读取价格和等级,不存,省空间。
    begin
    read(v,p); sum:=v*p; //价值就是2个数乘积
    for j:=n downto v do
    data[j]:=max(data[j],data[j-v]+sum); //01背包的动态转移方程
    end;

    write(data[n]); //答案
    end.

  • 0
    @ 2014-12-09 19:42:46

    var
    f:array[0..30000] of longint;
    n,m,i,j:longint;
    a,b:array[0..25] of longint;
    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]<f[j-a[i]]+a[i]*b[i] then
    f[j]:=f[j-a[i]]+a[i]*b[i];
    writeln(f[n]);
    end.

  • 0
    @ 2014-10-29 16:35:05

    var
    i,j,n,m,l,k:longint;
    a,b,f:array[1..30000] of longint;
    begin
    readln(m,n);
    for i:= 1 to n do
    begin
    readln(a[i],b[i]);
    b[i]:=b[i]*a[i];
    end;
    for i:=1 to n do
    for j:=m downto 1 do
    if j>a[i] then
    begin
    if f[j]<f[j-a[i]]+b[i] then
    f[j]:=f[j-a[i]]+b[i];
    end;
    writeln(f[m]);
    end.

  • 0
    @ 2014-08-16 18:59:00

    编译成功

    foo.pas(15,17) Warning: Variable "f" does not seem to be initialized
    测试数据 #0: Accepted, time = 0 ms, mem = 1176 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1172 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1172 KiB, score = 10
    测试数据 #3: Accepted, time = 11 ms, mem = 1168 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 1172 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 1168 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 1172 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 1168 KiB, score = 10
    Accepted, time = 71 ms, mem = 1176 KiB, score = 100

信息

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