POJ 1276 Cash Machine DP(多重背包化01背包）

本文主要是介绍POJ 1276 Cash Machine DP(多重背包化01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意: 现在需要价格总额为cash的钱,有version种面值的钱币,每种钱币的数目为amount,面值为denomination,求解在小于或等于所需价格总额的情况下所能组成的最大价值总和.
题解：每一种货币面值乘以系数1,2,4,...,2^(k-1), amount-2^k+1，且 k 是满足amount-2^k+1>0的最大整数。例如，如果amout为13，就将面值分别乘以系数1,2,4,6的得到四个值。然后将多重背包转化为01背包。

#include <iostream>
using namespace std;int dp[100005], c[10001];int main()
{int cash, version, denomination, amount;while ( cin >> cash ){int i, j, temp, k = 0;cin >> version;for ( i = 0; i < version; i++ ){cin >> amount >> denomination;j = 1;while ( j <= amount ){c[k] = j * denomination;amount -= j;j = j * 2;k++;}if ( amount > 0 )c[k++] = amount * denomination;}memset ( dp, 0, sizeof(dp) );for ( i = 0; i < k; i++ ){for ( j = cash; j >= c[i]; j-- ){temp = dp[j-c[i]] + c[i];if ( temp > dp[j] )dp[j] = temp;}}cout << dp[cash] << endl;}return 0;
}

这篇关于POJ 1276 Cash Machine DP(多重背包化01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---