vector<int> dp(100002);

class node
{
public:
        int count;   //每个币种的数目
	int num;     //面值
}Nodes[1001];

int t[11] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};

int main()
{
	int cashes, m;
	while(cin >> cashes >> m)
	{
		fill(dp.begin(), dp.begin() + cashes + 2, 0);
		for(int i = 1; i <= m; i++)
		{
			cin >> Nodes[i].count >> Nodes[i].num;
		}

		for(int i = 1; i <= m; i++)
		{
			if(Nodes[i].count * Nodes[i].num >= cashes)
			{
				for(int j = Nodes[i].num; j <= cashes; j++)
				{
					dp[j] = max(dp[j], dp[j - Nodes[i].num] + Nodes[i].num);
				}
			}
			else
			{
				int k = 0;
				int amount = Nodes[i].count;
				while(t[k] < amount)
				{
					for(int j = cashes; j >= t[k] * Nodes[i].num; j--)
					{
						dp[j] = max(dp[j], dp[j - t[k] * Nodes[i].num] + t[k] * Nodes[i].num);
					}
					amount -= t[k];
					k++;
				}
				for(int j = cashes; j >= Nodes[i].count * Nodes[i].num; j--)
				{
					dp[j] = max(dp[j], dp[j - Nodes[i].count * Nodes[i].num] + Nodes[i].count * Nodes[i].num);
				}
			}
		}
		cout << dp[cashes] << endl;
	}
	return 0;
}

• Re:我用背包问题9讲上的多重背包的伪代码写的，怎么一直过不了，各位大牛看看，谢谢！ (14) shangmin 2009-06-19 14:50:03
  • Re:我用背包问题9讲上的多重背包的伪代码写的，怎么一直过不了，各位大牛看看，谢谢！ (33) sjb358714 2009-08-22 16:35:52
• Re:我用背包问题9讲上的多重背包的伪代码写的，怎么一直过不了，各位大牛看看，谢谢！ (1265) asuran 2009-10-13 02:34:23