3月13日 背包问题

01背包

#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[31],c[31];
int f[2001];
int main(){
    scanf("%d%d",&m,&n);  //背包容量m 物品数量n
    for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);  //每个物品的重量和价值
    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--)
            if(f[j-w[i]]+c[i]>f[j])
                f[j]=f[j-w[i]]+c[i];
    printf("%d",f[m]);
    return 0;
}

完全背包

#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[31],c[31];
int f[2001];
int main(){
    scanf("%d%d",&m,&n);  //背包容量m 物品数量n
    for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);  //每个物品的重量和价值
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=m;j++)
            if(f[j-w[i]]+c[i]>f[j])
                f[j]=f[j-w[i]]+c[i];
    printf("%d",f[m]);
    return 0;
}