259 条题解

  • 0
    @ 2015-09-23 20:47:01

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int max(const int&a,const int&b)
    {
    if(a>b)return a;
    else{
    return b;
    }
    }
    int main()
    {
    int m,n,i,j,v,w[101],c[1001],f[101][1001];
    scanf("%d%d",&m,&n);
    for(i=1;i<=m;i++){
    scanf("%d%d",&w[i],&c[i]);
    }
    for(i=1;i<=m;i++){
    for(v=n;v>=1;v--){
    if(c[i]>v){
    f[i][v]=f[i-1][v];
    }
    else{
    f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]);
    }
    }
    }
    printf("%d",f[m][n]);
    }

  • 0
    @ 2015-09-01 17:27:12

    ###C++ Code
    #include <iostream>
    #include <cstdio>
    using namespace std;
    const int MAXN = 1000 + 5;
    int n,t,v,w,dp[MAXN]={0};
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>n>>t;

    for(int i=1;i<=n;i++)
    {
    cin>>v>>w;
    for(int j=t;j>=w;j--)
    dp[j]=max( dp[j-w] + v , dp[j] );
    }

    cout<<dp[t];
    return 0;

    }

  • 0
    @ 2015-08-31 00:20:59

    #include<stdio.h>
    #include<vector>

    #define max(a,b) a>b?a:b;

    std::vector<int>d;

    int main()
    {
    int n, C;
    int V, W;
    int i;
    while(scanf("%d%d", &n, &C) == 2) //循环好像没用
    {
    for(i=0;i<=C;++i)
    d.push_back(0);

    for(i=0; i<n; ++i)
    {
    scanf("%d%d", &W, &V);
    for(int j=C; j>=V; --j)
    d[j] = max(d[j], d[j-V]+W);
    }
    printf("%d\n", d[C]);
    }
    return 0;
    }

  • 0
    @ 2015-08-31 00:07:44

    #include <iostream>
    #include <vector>

    using namespace std;

    int N,t;
    vector<int>n,m,f;
    int i,j;

    int main()
    {
    cin>>N>>t;
    for(i=0;i<N;++i)
    {
    cin>>j;
    n.push_back(j);
    cin>>j;
    m.push_back(j);

    }
    for(i=0;i<=t;++i)
    f.push_back(0);

    for(j=0;j<N;++j)
    for(i=t;i>=0;--i)
    if(i>=m[j])
    if(f[i]<f[i-m[j]]+n[j])f[i]=f[i-m[j]]+n[j];
    cout<<f[t];
    return 0;
    }

  • 0
    @ 2015-07-11 22:39:14

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=10005;
    typedef long long ll;
    #define Max(a,b) (a>b)?a:b
    int n,W;
    ll dp[N][N];
    ll v[N];
    ll w[N];
    int main()
    {
    cin>>n>>W;
    for(int i=0;i<n;i++)
    {
    int de;
    cin>>v[i]>>w[i];
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<=W;j++)
    if(j<w[i])
    dp[i+1][j]=dp[i][j];
    else
    dp[i+1][j]=Max(dp[i][j],dp[i][j-w[i]]+v[i]);
    cout<<dp[n][W];

    return 0;
    }
    哪位大神指教一下,哪错了?

  • 0
    @ 2015-03-07 16:43:15

    /*************************************************************************
    > File Name: pack_2.c
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: 2015/3/7 16:31:02
    ************************************************************************/

    #include<stdio.h>
    #include<string.h>

    #define max(a,b) a>b?a:b;

    int main()
    {
    int n, C;
    int V, W;
    static int d[1000];
    while(scanf("%d%d", &n, &C) == 2) {
    memset(d, 0, sizeof(d)/sizeof(int));

    for(int i=0; i<n; ++i) {
    scanf("%d%d", &W, &V);
    for(int j=C; j>=V; --j)
    d[j] = max(d[j], d[j-V]+W);
    }
    printf("%d\n", d[C]);
    }
    return 0;
    }

    • @ 2015-08-31 00:03:34

      while有用吗??

    • @ 2015-08-31 00:23:09

      把d[1000]数组换成滚动数组,为什么内存变大了??

  • 0
    @ 2015-03-07 16:43:09

    /*************************************************************************
    > File Name: pack_2.c
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: 2015/3/7 16:31:02
    ************************************************************************/

    #include<stdio.h>
    #include<string.h>

    #define max(a,b) a>b?a:b;

    int main()
    {
    int n, C;
    int V, W;
    static int d[1000];
    while(scanf("%d%d", &n, &C) == 2) {
    memset(d, 0, sizeof(d)/sizeof(int));

    for(int i=0; i<n; ++i) {
    scanf("%d%d", &W, &V);
    for(int j=C; j>=V; --j)
    d[j] = max(d[j], d[j-V]+W);
    }
    printf("%d\n", d[C]);
    }
    return 0;
    }

  • 0
    @ 2015-03-07 16:06:02

    /*************************************************************************
    > File Name: 1025.c
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: 2015/3/7 15:41:02
    ************************************************************************/

    #include<stdio.h>
    inline int max(int a, int b) {
    return a>b?a:b;
    }

    int main()
    {
    int N, T;
    static int f[105], t[105];
    static int d[105][1005];
    while(scanf("%d%d", &N, &T) == 2) {
    for(int i=0; i<N; ++i)
    scanf("%d%d", &f[i], &t[i]);
    for(int i=0; i<=N; ++i)
    for(int j=0; j<=T; ++j) {
    d[i][j] = i==0?0:d[i-1][j];
    if(i>0 && j>=t[i-1]) d[i][j] = max(d[i-1][j], d[i-1][j-t[i-1]]+f[i-1]);
    }
    printf("%d\n", d[N][T]);
    }

    return 0;
    }

  • 0
    @ 2015-03-07 16:04:32

    /*************************************************************************
    > File Name: 1025.c
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: 2015/3/7 15:41:02
    ************************************************************************/

    #include<stdio.h>
    inline int max(int a, int b) {
    return a>b?a:b;
    }

    int main()
    {
    int N, T;
    static int f[105], t[105];
    static int d[105][1005];
    while(scanf("%d%d", &N, &T) == 2) {
    for(int i=0; i<N; ++i)
    scanf("%d%d", &f[i], &t[i]);
    for(int i=0; i<=N; ++i)
    for(int j=0; j<=T; ++j) {
    d[i][j] = i==0?0:d[i-1][j];
    if(i>0 && j>=t[i-1]) d[i][j] = max(d[i-1][j], d[i-1][j-t[i-1]]+f[i-1]);
    }
    printf("%d\n", d[N][T]);
    }

    return 0;
    }

  • 0
    @ 2015-02-15 21:47:37

    #include<stdio.h>

    #define max 100
    #define maxweight 1000

    int Max(int x,int y);
    int main()
    {
    int i,j,volume,n;
    int w[max+10],v[max+10];
    int m[max+10][maxweight+10];

    scanf("%d",&n);
    scanf("%d",&volume);
    for(i = 1;i <= n; i++)
    {
    scanf("%d",&v[i]);
    scanf("%d",&w[i]);
    }

    for(j = w[n];j <= volume; j++)
    m[n][j]=v[n];
    for(j = 0;j < w[n]; j++)
    m[n][j]=0;

    for(i = n-1;i >= 1; i--)
    {
    for(j = volume;j >= 1; j--)
    {
    if(j >= w[i])
    {
    m[i][j]=(m[i+1][j]>m[i+1][j-w[i]]+v[i])?m[i+1][j]:m[i+1][j-w[i]]+v[i];
    }
    else if(j < w[i])
    m[i][j]=m[i+1][j];
    }
    }
    printf("%d",m[1][volume]);
    return 0;
    }

    int Max(int x,int y)
    {
    if(x>=y)
    return x;
    else
    return y;
    }

  • 0
    @ 2015-02-01 23:01:31

    简单背包:滚动数组:空间优化,我忘了空间优化;但是这样可读性更强。
    动规的优化:1003 过河状态压缩 与此题一样都可以进行空间优化。
    #include<iostream>
    using namespace std;
    int a[1003][103];
    int time[103], like[103];
    int size, t;
    void go(){
    int i, j;
    for (i = 0; i < size; i++)a[0][i] = 0;
    for (i = 0; i < t; i++) a[i][size] = 0;
    for (j = size - 1; j >= 0; j--){
    for (i = 1; i <= t; i++){
    a[i][j] = 0;
    if (i >= time[j]){
    a[i][j] = like[j] + a[i - time[j]][j + 1];
    }
    if (a[i][j] < a[i][j + 1])
    a[i][j] = a[i][j + 1];
    }
    }
    cout << a[t][0] << endl;
    }
    int main(){
    //freopen("in.txt", "r", stdin);
    cin >> size >> t;
    int i;
    for (i = 0; i < size; i++)cin >> like[i] >> time[i];
    go();
    return 0;
    }

  • 0
    @ 2015-01-17 16:46:45

    01背包的解题公式,见到这种题直接复制就行了,因为顺序搞反了,我的AC率!!

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

  • 0
    @ 2015-01-16 21:20:09

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 744 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 744 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 748 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 748 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 748 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 748 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 744 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 748 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 748 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 748 KiB, score = 10
    Accepted, time = 15 ms, mem = 748 KiB, score = 100
    想当初,洒家费了多大劲,还死得那么惨,今日总算AC了!

  • 0
    @ 2015-01-14 17:43:55

    我擦,把我的采药这道题的AC程序直接复制过来,然后换下读入顺序,因为他是先读价值再读容量,妈呀,直接AC了居然!

    block code

    program P1104;
    uses math;
    var t,m,i,a,b,ans,j:longint;
    data:array[0..1000] of longint;
    begin
    read(m,t); ans:=0; fillchar(data,sizeof(data),0);
    for i:=1 to m do
    begin
    read(b);read(a);
    for j:=t downto a do
    begin
    data[j]:=max(data[j],data[j-a]+b);
    end;
    end;

    write(data[t]);
    end.

  • 0
    @ 2014-11-30 15:08:09

    #include<cstdio>
    using namespace std;
    int n,t,v[101],w[101],f[1001],i,j;
    int main()
    {

    scanf("%d%d",&n,&t);
    for(i = 1 ; i <= n ; i ++)
    scanf("%d%d",&w[i],&v[i]);
    for(i = 1 ; i <= n ; i ++)
    for(j = t ; j >= 1 ; j --)
    if(f[j]>f[j-v[i]]+w[i]||j-v[i]<0);
    else f[j]=f[j-v[i]]+w[i];
    printf("%d",f[t]);
    }

  • 0
    @ 2014-07-14 15:31:23

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define IOFileName "P1025"
    const int maxt=1002;
    int n,t,fi,ti;
    int T[maxt]={0};
    int main(){
    //freopen(IOFileName".in","r",stdin);
    //freopen(IOFileName".out","w",stdout);
    scanf("%d\n%d\n",&n,&t);
    for(int i=0;i<n;i++){
    scanf("%d %d\n",&fi,&ti);
    for(int j=t;j>=0;j--){
    if((T[j]&&j+ti<=t)||j==0){
    T[j+ti]=max(T[j+ti],T[j]+fi);
    }
    }
    }
    printf("%d\n",*max_element(T,T+t+1));
    }
    252MB+15MS

  • 0
    @ 2014-04-07 22:11:40

    3次WA...

  • 0
    @ 2014-04-07 21:54:16

    跪求啊

  • 0
    @ 2014-04-07 21:52:04

    我基础烂,新手一枚,为了比赛,有人教我错在哪儿吗??谢谢。
    read(n,m);
    for i:=1 to n do
    begin
    readln(t1[i],t2[i]);
    end;
    for i:=1 to n do
    begin
    t3[i]:=t2[i]/t1[i];
    end;
    repeat
    for i:=1 to n do
    begin
    if t3[i]<t3[i+1] then h:=t3[i]; t3[i]:=t3[i+1]; t3[i+1]:=h;
    h:=t2[i]; t2[i]:=t2[i+1]; t2[i+1]:=h;
    h:=t1[i]; t1[i]:=t1[i+1]; t1[i+1]:=h;
    end;
    until t2[i]>=t2[i+1];
    for i:=1 to n do
    begin
    if (m>=t1[i]) then y:=y+t2[i]; m:=m-t1[i];
    end;
    write(y:0:0);
    end.

  • 0
    @ 2014-01-01 11:58:41

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

信息

ID
1025
难度
4
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
9921
已通过
4043
通过率
41%
被复制
13
上传者