coin-change

发表于   |  

##练习

练习1：UVA 674
有1，5，10，25，50这五种硬币。给一个价值target，求有多少种组合可以得到该价值。
完全背包问题，硬币类型给定，数量不限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Count(int n, int m) { 
    // n:the total sum of money, m:the kinds of conis
    // use first m kinds coins to exchange n yuan
    // num[i] will be storing the number of solutions for value i. 
    // We need n+1 rows as the table is consturcted in bottom up manner using the base case (n = 0)
    // Base case (If given value is 0)
    num[0] = 1;

    // Pick all coins one by one and update the num[] values
    // after the index greater than or equal to the value of the
    // picked coin
    for(int i=0; i<m; i++)
        for(int j=kind[i]; j<=n; j++)
            num[j] += num[j- kind[i]];
    
    return num[target]; // target is the aimed money to exchange
}

练习2：UVA 147
和练习1基本一样求方案数，完全背包问题，此题注意浮点数精度问题（加上个0.5）。

1
2
3
4
num[0] = 1;
for (int i=0; i<m; i++)
    for (int j=kind[i]; j<n; j++)
        num[j] += num[j - kind[i]];

练习3：UVA 166
硬币类型已知，我要去商店买东西。商店硬币数量无限，我携带硬币数量有限，并给出每类硬币具体数量。
给定要付的金额，问付钱找钱过程中最少使用几枚硬币？

商店硬币无限，计算凑i元前最少使用硬币数，即shopmin[i]，完全背包问题
我的硬币有限，计算凑i元前最少使用硬币数，即mymin[i],多重背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void countShop(){
    shopmin[0] = 0;
    for (int i=1; i<MAXMONEY; i++)
        shopmin[i] = 9999;  //just a large nuber
    for (int i=0; i<MAXCOIN; i++) {
        for (int j=kind[i]; j<MAXMONEY; j++) {
            shopmin[j] = Math.min(shopmin[j-kind[i]]+1, shopmin[j]);
	   }
	}
}

void countMy(){ // eachcoin[]: numbers of each coin
    mymin[0] = 0;
    for (int i=1; i<MAXMONEY; i++)
       mymin[i] = 9999;
    for (int c=0; c<MAXCOIN; c++) {
        while (eachcoin[c] > 0) {
            for (int i=MAXMONEY-kind[c]-1; i>=0; i--) {
                if (mymin[i] < 9999)
                    mymin[i+kind[c]] = Math.min(mymin[i]+1, mymin[i+kind[c]]);
            }
            eachcoin[c]--;
        }
    }
}

int findAns(){
    int ans = 9999;
    for (int i=charge; i<MAXMONEY; i++){
        if (9999 != mymin[i]){
            ans = Math.min(ans, mymin[i]+shopmin[i-charge]);
        }
    }
    return ans;
}

练习4：UVA 10306

define dp[i][j]: the least coins to make i yuan and j yuan
if i^2+j^2=target^2 then dp[i][j] is a answer

练习5：UVA 10313

define dp[i][j]: the count to use no more than j money coin making up to i yuan
dp[i][j] = dp[i-j][j] + dp[i][j-1]

Loading…

##Reference
背包问题的变化——求方案数
背包九讲