ybt背包

QLWybz / 2024-02-06 / 原文

ybt背包

01背包

从后往前枚举，小心我们的答案被覆盖。

for(int i=1;i<=n;i++)
	for(int j=t;j>=a[i];j--){
	f[j]=max(f[j],f[j-a[i]]+v[i]);
}

采药问题

这就是一个01背包的经典题。

#include <bits/stdc++.h>
using namespace std;
int t, m, dp[1010], w[110], v[110];
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> m;
    for (int i = 1; i <= m; i++) 
        cin >> w[i] >> v[i];
    for (int i = 1; i <= m; i++) {
        for (int j = t; j >= w[i]; j--) 
            dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
    }
    cout << dp[t];
    return 0;
}

完全背包

就是一个东西可以取若干个。

    for (int i=1;i<=N;i++)
        for (int j=v[i];j<=V;j++)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

就把这个$j$的$for$循环转过来

货币系统

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], maxx, ans, vis[25000], f[25000], t;
int main() {
    scanf("%d", &t);
    while (t--) {
        maxx = ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= 25000; i++) vis[i] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            maxx = max(maxx, a[i]);
        }
        sort(a + 1, a + 1 + n);
        for (int i = 1; i <= n; i++) {
            if (vis[a[i]])
                continue;
            ans++, vis[a[i]] = 1;
            for (int k = a[i]; k <= maxx; k++) {
                if (vis[k - a[i]])
                    vis[k] = 1;
            }
        }
        printf("%d\n", ans);
    }
}

多重背包

有数量限制

例题

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
    int T,n,m;
    int v[105],w[105],num[105],dp[105];
    cin>>T;
    while(T--)
    {
        cin>>m>>n;
        for(int i=0;i<n;i++)
            cin>>v[i]>>w[i]>>num[i];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
            for(int j=0;j<num[i];j++)
                for(int k=m;k>=v[i];k--)
                    dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
        cout<<dp[m]<<endl;
    }
    return 0;
}

二进制优化

struct Node {
    int v, w;
};
 
vector<Node> V;//最好使用vector 因为你不容易便确定拆完后需要多少空间
 
for (int i = 0; i < n; i++) {
    int w, v, s;
    cin >> w >> v >> s;
    for (int j = 1; j <= s; j <<= 1) {
        s -= j;
        V.push_back({v * j, w * j});
    }
    if (s > 0) V.push_back({v * s, w * s});//有余数就直接加进去
}
 
for (int i = 0; i < V.size(); i++) {
    for (int j = m; j >= V[i].w; j--)
        dp[j] = max(dp[j], dp[j - V[i].w] + V[i].v);
}

宝物筛选

#include <bits/stdc++.h>
using namespace std;
int n, W;
struct node {
    int v, w;
};
vector<node> vec;
int dp[100010];
int main() {
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        int w, v, s;
        cin >> v >> w >> s;
        for (int j = 1; j <= s; j <<= 1) {
            s -= j;
            vec.push_back((node){ v * j, w * j });
        }
        if (s)
            vec.push_back((node){ v * s, w * s });
    }
    for (int i = 0; i < vec.size(); i++) {
        for (int j = W; j >= vec[i].w; j--) dp[j] = max(dp[j], dp[j - vec[i].w] + vec[i].v);
    }
    cout << dp[W] << endl;
    return 0;
}

例题：

硬币方案

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int f[100005],b[100005],a[103][2],ans;
int main()
{
	cin>>n>>m;
	while (n!=0||m!=0)
	{
		ans=0;
		memset(f,0,sizeof(f));
		f[0]=1;
		for (int i=1;i<=n;i++) cin>>a[i][0];
		for (int i=1;i<=n;i++) cin>>a[i][1];
		for (int i=1;i<=n;i++)
		{
			memset(b,0,sizeof(b));
			for (int j=a[i][0];j<=m;j++)
			{
				if (f[j]==0&&b[j-a[i][0]]<a[i][1]&&f[j-a[i][0]]) b[j]=b[j-a[i][0]]+1,f[j]=1,ans++;//把b初始化，重要思想
			}
		}
		cout<<ans<<endl;
        cin>>n>>m;
	}
	return 0;
}