题意：
给你一个容量为n的背包，和数量为m的物品，每件物品有价值和重量，并且可以取无数次，问你怎样取得最小值，并把重量取满。
思路：
一开始写了一个01背包，稍微改了一下变成完全背包了，不过被卡空间了。
然后看了一下讨论区是用完全背包写的，就去学习了一下完全背包的做法，和优化空间。
这题就是一个裸的完全背包把dp初始化inf就行了。滚动数组优化空间也挺简单的。
代码：(01背包卡空间版本)



#include<bits/stdc++.h>
using namespace std;

int n;
const int maxn = 1e4 + 10;
struct node{
    int v,w;
    node(){}
    node(int a,int b):v(a),w(b){}
}a[1100];
int dp[maxn][maxn],weight[maxn][maxn]; 
//dp[i][j]:容量为i的前j件物品的最小价值 
int main(){
    int t;cin>>t;
    while(t--){
        int e,f;cin>>e>>f;
        cin>>n;
        for(int i = 1; i <= n; i++){
            cin>>a[i].v>>a[i].w;
        }
        int m = f - e;
        memset(dp,0,sizeof(dp));
        memset(weight,0,sizeof(weight));
        for(int i = 1; i <= m; i++){
            if(i >= a[1].w){
                dp[i][1] = a[1].v + dp[i - a[1].w][1];
                weight[i][1] = weight[i - a[1].w][1] + a[1].w;
            }
        }
        for(int i = 1; i <= m ; i++){//枚举容量 
            for(int j = 2; j <= n; j++){//枚举物品 
                if(a[j].w <= i){
                    int l = dp[i][j - 1];
                    int r = dp[i - a[j].w][j] + a[j].v;
                    if(l < r){
                        dp[i][j] = l;
                        weight[i][j] = weight[i][j - 1];
                    }else{
                        dp[i][j] = r;
                        weight[i][j] = weight[i - a[j].w][j] + a[j].w;
                    }
                } else{
                    dp[i][j] = dp[i][j - 1];//这个物品不放 
                    weight[i][j] = weight[i][j - 1];
                }
            }
        }
        if(weight[m][n] == m){
            cout<<"The minimum amount of money in the piggy-bank is "<<dp[m][n]<<"."<<endl;
        }else{
            cout<<"This is impossible."<<endl;
        }
    }
}

完全背包ac版本：

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e4 + 10; 
int v[maxn],w[maxn]; 
int dp[maxn];
int main(){
    int t ;
    cin>>t;
    while(t--){
        int e , f;cin>>e>>f;
        int n = f - e;
        int m;cin>>m;
        for(int i = 1; i <= m; i++)cin>>v[i]>>w[i];
        memset(dp,0x3f,sizeof(dp));
        dp[0] = 0;
        for(int i = 1; i <= m; i++){
            for(int j = n; j >= 1; j--){
                for(int k = 0; k <= j/w[i]; k++){
                    dp[j] = min(dp[j],dp[j - k * w[i]] + k * v[i]);
                }
            }
        }
        if(dp[n] == inf)cout<<"This is impossible."<<endl;
        else cout<<"The minimum amount of money in the piggy-bank is "<<dp[n]<<"."<<endl; 
    }
}

最终优化版本：

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e4 + 10; 
int v[maxn],w[maxn]; 
int dp[maxn];
int main(){
	int t ;
	cin>>t;
	while(t--){
		int e , f;cin>>e>>f;
		int n = f - e;
		int m;cin>>m;
		for(int i = 1; i <= m; i++)cin>>v[i]>>w[i];
		memset(dp,0x3f,sizeof(dp));
		dp[0] = 0;
		for(int i = 1; i <= m; i++)
		for(int j = w[i]; j <= n; j++)
		dp[j] = min(dp[j],dp[j - w[i]] + v[i]);
		if(dp[n] == inf)cout<<"This is impossible."<<endl;
		else cout<<"The minimum amount of money in the piggy-bank is "<<dp[n]<<"."<<endl; 
	}
}