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をそれぞれ乗じた4つの値が得られる.その後、多重リュックを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;
}