andalousie

我成功AC的头一个DP

热度 3已有 474 次阅读2014-2-20 22:52 |个人分类:鱼C日志

我很久以前就开始做我们学校OJ上面的题。做到1003的时候还兴致勃勃地学习了背包问题。那是去年的一个秋天，我改了许久，终于出正确答案了。交上去。。。Wrong Answer。再次改了，仍然WA。现在重新改正并且成功提交了。

这是题目链接。打开1003题即为这道背包问题。

我的代码如下：

#include <iostream>

int N, K, G[11], W[11];

int F[15001];

inline int CompletePack(int *F, int *G, int *W)

{

for (int i = 0; i <= N; ++i)

F[i] = 0;

for (int i = 1; i <= K; ++i)

for (int v = G[i]; v <= N; ++v)

if(F[v - G[i]] + W[i] > F[v])

F[v] = F[v - G[i]] + W[i];

return F[N];

}

int main()

{

while(std::cin >> N >> K)

{

for (int i = 1; i <= K; ++i)

{

std::cin >> G[i] >> W[i];

}

int result = CompletePack(F, G, W);

std::cout << result << std::endl;

}

return(0);

}

账号		自动登录	找回密码
密码			立即注册