背包问题（如何定义dp状态）

前言：我们要如何定义dp的定义呢，我们不能像正常那样，定义为花费了 i 钱得到的最大收益，我们这一题需要的是收益为 i 的时候的最小花费，那么我们就需要定义为达到收益为 v 的时候的最小花费

---

这一题有一个难点就是，我们收益大于当前的 i 值的时候，也要当作 i 进行转移

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

#define int long long
const int N = (int)1e3+10;
int b[N],c[N];
int n,m,v;
vector<int> sto[N];

bool cmp(int a,int b){
    return a>b;
}
// 考虑用
signed main(){
    cin>> n >> m >> v;
    for(int i=0;i<n;i++){
        cin >> b[i] >> c[i];
    }
    for(int i=1;i<=m;i++){
        int a,t;
        cin >> a >> t;
        sto[t].push_back(a);
    }
    // 从大到小排序
    for(int i=0;i<n;i++){
        sort(sto[i].begin(),sto[i].end(),cmp);
    }
    vector<int> bag(v+10,0x3f3f3f3f);
    bag[0] = 0;
    for(int i=0;i<n;i++){
        if(sto[i].size()==0) continue;
        for(int j=v;j;j--){
            int now = 0; int cost = b[i];
            for(int k=0;k<sto[i].size();k++){
                now += sto[i][k]; cost += c[i];
                int d = now - cost;
                if(d<=0) break;
                d = min(d,j);
                bag[j] = min(bag[j],bag[j-d]+cost);
            }
        }
    }
    cout << bag[v];
    system("pause");
    return 0;
}

原文地址：https://blog.csdn.net/wniuniu_/article/details/142308465

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！