01背包问题（两种状态）UVa-12563 - Jin Ge Jin Qu hao

本文主要是介绍01背包问题（两种状态）UVa-12563 - Jin Ge Jin Qu hao，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题 https://vjudge.net/problem/UVA-12563

对于每移动一步都有两种状态，创建了两个数组来维护状态进行状态转移，也可用一个结构体，这两种状态为结构体的成员函数类似于http://blog.csdn.net/u013480600/article/details/40376143的思路

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int time_[5555] = {0};
int dp[255555] = {0};int main()
{int n;while (cin >> n && n != -1){memset(time_, 0, sizeof(time_));memset(dp, 0, sizeof(dp));int index = 0;int len = 0;while (n--){int v, c;cin >> v >> c;len += v * c;{time_[index++] = v;}while (c--)}for (int i = 0; i < index; i++){for (int j = len / 2; j >= time_[i]; j--)// for (int j = 0; j <= len / 2; j++){dp[j] = max(dp[j], dp[j - time_[i]] + time_[i]);}}cout << len - dp[len / 2] << " " << dp[len / 2] << endl;}return 0;
}

这篇关于01背包问题（两种状态）UVa-12563 - Jin Ge Jin Qu hao的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---