背包问题汇总

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int V;
void zeroonepack(vector<int> &result, vector<int> v, vector<int> value, int i)
{
	for (int j = V; j >= v[i]; --j)
	{
		j < v[i] ? result[j] = result[j] : result[j] = max(result[j], result[j - v[i]] + value[i]);//放不下第i个物体
	}
	return;
}
int main()
{
	int n, temp1, temp2, temp3, k = 1;//背包体积V，n组数
	cin >> V >> n;
	vector<int> num(n + 1, 0),v(1, 0), value(1, 0), result(V + 1, 0);/*v是物体体积，value是物体价值。result[i]表示前i个物品，
	放到v中最大价值,需要初始化为0。如果需要刚好放满背包，除了第0个元素，其他要初始化为负无穷。v和value只申请一个是因为第0个要为0*/
	for (int i = 1; i <= n; ++i)
	{
		cin >> temp1 >> temp2 >> temp3;
		num[i] = temp1;
		while (k < num[i])//未进入循环的时候，即等于原num[i]-2^k+1
		{
			v.push_back(k*temp2);
			value.push_back(k*temp3);
			num[i] -= k;
			k = k * 2;
		}
		v.push_back(num[i] * temp2);
		value.push_back(num[i] * temp3);//补差值
        k=1;
	}
	for (int i = 1; i <= v.size(); ++i)//二进制优化01背包后，有v.size()个物品
		zeroonepack(result, v, value, i);
	cout << result[V] << endl;
	return 0;
}

#include<iostream>
#include <vector>
using namespace std;
int result, n, temp;
long long v;
vector<long long>zq;
void dfs(int step,long long sum)
{
    result++;
    if(step==n)
       return;
    for (int i = step; i < n; ++i)
        if (sum + zq[i] <= v)
            dfs(i+1, sum +zq[i]);
    return;
}
int  main()
{
    long long kk=0;
    cin >> n>>v;
    for (int i = 0; i < n; ++i)
    {
        cin >> temp;
        zq.push_back(temp);
        kk += temp;
    }
    if (kk <= v)
        result = 1 << n;
    else
         dfs(0,0);
    cout << result<<endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int kindCount = 0;
    int capacity = 0;
    cin >> capacity >> kindCount;

    vector<int> cost;
    cost.push_back(0);

    for(int i = 0;i < kindCount;i++){
        int tmp = 0;
        cin >> tmp;
        cost.push_back(tmp);
    }

    vector<int> dp(capacity + 1,0);
    dp[0] = 1;

    for(int i = 1;i <= kindCount;i++){
        for(int j = capacity;j >= 0;j--){
            if(j >= cost[i]){
                dp[j] = dp[j] + dp[j - cost[i]];
            }
        }
    }
    for(int i = 0;i <= capacity;i++){
        cout << dp[i] << " ";
    }
    cout << endl;
    cout << dp[capacity] << endl;
}

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int kindCount = 0;
    int capacity = 0;
    cin >> kindCount >> capacity;

    vector<int> cost;
    cost.push_back(0);

    vector<int> lineTmp(capacity + 1,0);
    vector<vector<int>> dp(kindCount + 1,lineTmp);
    dp[0][0] = 1;

    for(int i = 0;i <kindCount;i++){
        int costTmp = 0;
        cin >> costTmp;
        cost.push_back(costTmp);
    }

    for(int i = 1;i <= kindCount;i++){
        for(int j = 0;j <= capacity;j++){
            if(j == 0){
                dp[i][j] == 1;
            }
            if(cost[i] <= j){
                dp[i][j] = dp[i - 1][j] + dp[i][j-cost[i]];
            }
            if(cost[i] > j){
                dp[i][j] = dp[i - 1][j];
            }
            
        }
    }
    cout << dp[kindCount][capacity] << endl;
    for(int i = 0;i <= kindCount;i++){
        for(int j = 0;j <= capacity;j++){
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int kindCount = 0;
    int capacity = 0;
    cin >> capacity >> kindCount;

    vector<int> cost;
    vector<int> number;
    cost.push_back(0);
    number.push_back(0);

    for(int i = 0;i < kindCount;i++){
        int costTmp = 0;
        int numberTmp = 0;
        cin >> costTmp >> numberTmp;
        cost.push_back(costTmp);
        number.push_back(numberTmp);
    }
    vector<int> dp(capacity + 1);
    dp[0] = 1;
    for(int i = 1;i <= kindCount ;i++){
        for(int j = capacity;j >= 0;j--){
            for(int k = 1;k <= number[i];k++){
                if(j >= k*cost[i]){
                    dp[j] = dp[j] + dp[j - k * cost[i]];
                }
            }
        }
    }
    
    for(int i = 0;i <=capacity;i++){
        cout << dp[i] << " ";
    }
    cout << endl;
    cout << dp[capacity] << endl;
}