Multiple Knapsack Problem

problem link

The Meaning of the problem

You have three kinds of coins. Their face values are 1,2 and 5. Of cause you only have a limited number of coins. You need to find the minimum value that you can’t represent exactly with these coins.

Solution

There are lots of people solve this problem using Generating function. That way is too hard to understand. We just need to think of this problem as a multiple knapsack problem.

I learned from this blog

dp[j] = 1 means that j value can be represent by the coins.

Set dp[0] = 1 initially. And the transfer equation is dp[j] = max(dp[j],dp[j-k*money[i]])

Let’s assume there is only one 1 yuan coin, one 2 yuan coin and one 5 yuan coin. When d[j] need changing, we should see whether d[j-value] can be represent.

The top row of the table shows the total amount of money. The leftmost column of the table shows the face value of the coins.

Here’s the picture to show how the sequence is changed.

knapsack sheet

The top row of the table shows the total amount of money. The leftmost column of the table shows the face value of the coins.

The answer is i where dp[i] = 0.

Code

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
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
const int mxlen = 1e5+10;
int dp[mxlen];
int num[4];
int money[] = {0,1,2,5};
int main(){
    int n1,n2,n5;
    while(1){
        memset(dp,0,sizeof(dp));
        scanf("%d%d%d",&num[1],&num[2],&num[3]);        
        if(num[1]==0&&num[2]==0&&num[3]==0) break;
        int sum = num[1]+2*num[2]+5*num[3];
        dp[0] = 1;
        // 多重背包
        for(int i=1;i<=3;i++){
            // 倒序是因为我们转移需要上一层的数据，正序的话会改变值从而后面的值更新错误
            // 因为实际上这是用一维数组代替二维数组
            for(int j=sum;j>=money[i];j--){
                for(int k=1;k*money[i]<=j&&k<=num[i];k++){
                    dp[j] = max(dp[j],dp[j-k*money[i]]);
                }
            }
        }
        int ans = sum+1;
        for(int i=0;i<=sum;i++){
            if(!dp[i]) {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}