动态规划入门第3课,经典DP问题2 --- 背包问题_第1题 方案数 查看测评数据信息 给你n个整数,每个数可选或不选,要求选一些数,使它

给出储钱罐的重量，每种钱对应的重量和价值，求出储钱罐内至少有多少钱？                    

输入格式

  第一行为一个正整数T，表示T（T<=5）组测试数据。

每组数据:

第一行为两个正整数E，F（1<=E<=F<=10000），表示空的储钱罐的重量和装了钱后的重量。

第二行为一个正整数N（1<=N<=500），表示钱的种类数。

接着的N行每一行有两个正整数P,W（1<=P<=50000, 1<=W<=10000），表示钱的价值与重量。

输出格式

每组测试数据一行一个句子“The minimum amount of money in the piggy-bank is X.”X为至少有多少钱，如果无解，则输出“This is impossible.”（注意有英文句号）

输入/输出例子1

输入：

3

10 110

2

1 1

30 50

10 110

2

1 1

50 30

1 6

2

10 3

20 4

输出：

The minimum amount of money in the piggy-bank is 60.

The minimum amount of money in the piggy-bank is 100.

This is impossible.

样例解释

无

代码

#include <iostream>
#include <vector>
#include <limits>
 
int findMinimumAmount(int E, int F, int N, std::vector<std::pair<int, int> >& coins) {
    std::vector<int> dp(F + 1, std::numeric_limits<int>::max());
    
    dp[0] = 0;
    for (int j = 0; j < N; j++) {
    	for (int i = 1; i <= F; i++) {
            if (i >= coins[j].second && dp[i - coins[j].second] != std::numeric_limits<int>::max()) {
                dp[i] = std::min(dp[i], dp[i - coins[j].second] + coins[j].first);
            }
        }
    }
    
    return (dp[F-E] != std::numeric_limits<int>::max()) ? dp[F-E] : -1;
}
 
int main() {
    int T;
    std::cin >> T;
    
    while (T--) {
        int E, F;
        std::cin >> E >> F;
        
        int N;
        std::cin >> N;
        
        std::vector<std::pair<int, int> > coins(N);
        
        for (int i = 0; i < N; i++) {
            std::cin >> coins[i].first >> coins[i].second;
        }
        
        int result = findMinimumAmount(E, F, N, coins);
        
        if (result != -1) {
            std::cout << "The minimum amount of money in the piggy-bank is " << result << "." << std::endl;
        } else {
            std::cout << "This is impossible." << std::endl;
        }
    }
    
    return 0;
}

• 练习3 

#include<bits/stdc++.h>
using namespace std;
int N,M,d[510],c[510],ans = 0;
int nn,dd[10000],cc[10000];
int f[10000006];
int main(){
    cin>>N>>M;
    for(int i = 1;i <= N;i++){
        cin>>d[i];
    }
    for(int i = 1;i <= N;i++){
        cin>>c[i];
        if(c[i]>M/d[i]){
            c[i] = M/d[i];
        }
    }
    nn = 0;
    for(int i = 1;i <= N;i++){
        int x = c[i];
        for(int p2 = 1;x > p2;p2*=2){
            dd[++nn] = p2*d[i];
            cc[nn] = p2;
            x -= p2;
        }
        if(x > 0){
            dd[++nn] = x*d[i];
            cc[nn] = x;
        }
    }
    f[0] = 1;
    for(int i = 1;i <= nn;i++){
        for(int j = M-dd[i];j >= 0;j--){
            if(f[j]>0){
                if(f[j+dd[i]] == 0|| f[j+dd[i]]>f[j]+cc[i]){
                    f[j+dd[i]] = f[j]+cc[i];
                }
            }
        }
    }
    ans = f[M]-1;
    cout<<ans;
    return 0;
}