不找零钱

题目描述
牛可乐在牛牛商场买了一个帽子，要支付c元金币，牛牛商场一律不找零钱，牛可乐手里有不限数量的面值a元的金币和面值b元的金币，请问牛可乐可以用金币刚好凑出总价c元吗？

输入描述:
输入一行，包含三个整数a,b,c （a,b <= 100, c <= 10000）

输出描述:
输出一行,如果可以输出”Yes”,否则输出”No”.

示例1
输入：3 2 7
输出：Yes

解题思路：
这道题可以看成简单的一道背包问题，利用求解背包问题的动态规划方法进行求解。
问题描述可转成另一种描述：
假定有一个容量为 c 的背包，并且有两种物品，价值和容量相同分别为 a，b，每种物品都有无限件可用。求能否用这两种物品恰好装满背包。
这是一个完全背包问题，具体可参考背包问题九讲

C# 代码

using System;
class Program{
  static void Main(){
      string input;
      string[] tokens;
      while((input = Console.ReadLine()) != null){
          tokens = input.Split();
          int[] arr = new int[]{int.Parse(tokens[0]), int.Parse(tokens[1])};
          int c = int.Parse(tokens[2]);
          int[] dp = new int[c+1];
          foreach(int v in arr)
              for(int i = v; i <= c; i++)
                  dp[i] = Math.Max(dp[i], dp[i-v]+v);
          if(dp[c] == c) Console.WriteLine("Yes");
          else Console.WriteLine("No");
      }
  }
}