问题标题: 酷町堂：1206 黄金问题

Question

0

已解决

谢祎恒

中级守护

http://judge.codingtang.com/problem/1206/

#include<iostream>
#include<cstring>
using namespace std;
int n,v,c[1100],w[1100],F[1100];
int main()
{
    int i,j;
    while((cin>>n>>v) && (n>0 || v>0))
    {
        for(i=1;i<=n;i++)
        {
            cin>>c[i]>>w[i];
        }
        for(i=1;i<=n;i++)
        {
            for(j=v;j>=w[i];j--)
            {
                F[j]=max(F[j],F[j-c[i]]+w[i]);
            }
        }
        cout<<F[v]<<"\n";
        memset(F,0,sizeof(F));
    }
    return 0;
}

请帮忙找错，谢谢

Answer 1

已采纳

陆姗姗

资深守护

for(i=1;i<=n;i++)
{
for(j=v;j>=w[i];j--)
{
F[j]=max(F[j],F[j-c[i]]+w[i]);
}
}

第二个for循环的条件写错了,是j>=c[i],不是j>=w[i];

Answer 2

栾峻岩

初级天翼

你最好把F数组改成二维数组，最后输出：

F[n][v]

for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=v;j++)
        {
            if (w[i]>j)
            {
                f[i][j]=f[i-1][j]; 
            }
            else
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);//动态转移方程。
            }
        }
    }

Answer 3

朱小川

缔造者

动态规划

Answer 4

王子凡

高级光能

for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=v;j++)
        {
            if (j>=w[i])
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);//动态转移方程
            }
            else
            {
                f[i][j]=f[i-1][j];
            }
        }
    }
    if (n!=0 && v!=0)//判断n和v是不是0
        cout<<f[n][v];
    else
        cout<<endl;

麻烦你自己对对看

王子凡在2018-02-07 17:35:38追加了内容

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

最后再判断n,v是不是0 再输出就行了你再look look

Answer 5

蒋智航

高级天翼

这是动态规划

Answer 6

张睿杰

初级天翼

这道题可以用背包来解决，不用这么麻烦

Answer 7

刘凯南

高级守护

(n>0 || v>0)
改为(n!=0&&v!=>0)

问题标题: 酷町堂：1206 黄金问题

7 个回答: