牛牛们吃糖果

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // n 个牛牛
        int n = sc.nextInt();
        // m 颗糖果
        int m = sc.nextInt();
        // 每个牛牛吃到的糖果 a[i]
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
            if (a[i] < 1 || a[i] > 1000000) {
                return;
            }
        }
        int[] v = new int[a.length];
        Arrays.fill(v, 1);
        // k 个约定
        int k = sc.nextInt();
        //第 i 个牛牛与第 j 个牛牛有约定  
        for (int i = 0; i < k; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            a[x - 1] += a[y - 1];
            v[x - 1] += 1;
            v[y - 1] = 0;
        }
        int[] opt = new int[m + 1];
        Arrays.fill(opt, 0);
        for (int i = 0; i < n; i++) {
            if (v[i] == 0) {
                continue;
            }
            for (int j = m; j > a[i] - 1; --j) {
                opt[j] = Math.max(opt[j], (opt[j - a[i]] + v[i]));
            }
        }
        //最多能吃到糖果的牛牛个数
        System.out.print(opt[opt.length - 1]);
    }
}

0 - 1背包

• 糖果为体积, 牛的数量为价值, 求体积不超过m的最大价值
• 若第i头牛有约定, 则将i和j绑定成一个物品: 体积为a[i] + a[j], 价值为2; 否则i是体积为a[i],价值为1的物品

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int f[N];
int w[N], v[N];
bool st[N];

void solve(){
    int n, m, k;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> w[i];

    cin >> k;
    vector<int> ww, vv;
    for (int i = 1; i <= k; i ++ ) {
        int u, v;
        cin >> u >> v;
        ww.push_back(w[u] + w[v]), vv.push_back(2);
        st[u] = st[v] = true;
    }
    for (int i = 1; i <= n; i ++ ) 
        if (st[i] == false)
            ww.push_back(w[i]), vv.push_back(1);

    int nn = ww.size();

    for (int i = 0; i < nn; i ++ )
        for (int j = m; j >= ww[i]; j -- )
            f[j] = max(f[j], f[j - ww[i]] + vv[i]);
    cout << f[m] << endl;
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t -- )
        solve();
    return 0;
}

import java.util.*;
/*
    转换成01背包问题，然后利用动态规划
*/
public class Main{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        in.nextLine();
        int[] a = new int[n];
        String[] str = in.nextLine().split(" ");
        for(int i =0;i<n;i++)
        {
            a[i] = Integer.parseInt(str[i]);
        }
        int k = in.nextInt();
        boolean[] visit = new boolean[n];
        List arr = new ArrayList();
        for(int i =0;i<k;i++)
        {
            int b = in.nextInt()-1;
            int c = in.nextInt()-1;
            arr.add(new int[]{a[b]+a[c],2});
            visit[b] = true;
            visit[c] = true;
        }
        for(int i =0;i<n;i++)
        {
            if(!visit[i])
            {
                arr.add(new int[]{a[i],1});
            }
        }
        int[][] dp = new int[arr.size()][m+1];
        for(int i=0;i<=m;i++)
        {
            if(i>=arr.get(0)[0])
            {
                dp[0][i] = arr.get(0)[1];
            }
        }
        for(int i =1;i<arr.size();i++)
        {
            for(int j=0;j<=m;j++)
            {
                if(j>=arr.get(i)[0])
                {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-arr.get(i)[0]]+arr.get(i)[1]);
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[arr.size()-1][m]);
    }
}

贪心问题 注意细节处理

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[1005];

struct node{
    int num,info;
}Copy[1005];
int vis[1005];
bool cmp(const node& a, const node& b) {
//    return a.num<b.num;
    if (a.info==b.info){
        return a.num<b.num;
    }
    else if (a.info==1){
        return a.num<b.num*2;
    }
    else return a.num*2<b.num;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    cin>>k;
    int cnt=0;
    for (int i=0;i<k;++i){
        int l,r;
        cin>>l>>r;
        vis[l]=1,vis[r]=1;
//        cin>>t[i].l>>t[i].r;
//        t[i].num=a[t[i].l]+a[t[i].r]
//        vis[t[i].l]^=1,vis[t[i].r]^=1;
        Copy[cnt].num=a[l]+a[r];
        Copy[cnt++].info=1;
        }
    for (int i=1;i<=n;++i){
        if (!vis[i]){
            Copy[cnt++].num=a[i];
        }
    }
//    m*=2;
    int ans=0;
    sort (Copy,Copy+cnt,cmp);
    for (int i=0;i<cnt;++i){
        if (m>Copy[i].num) {
            if (Copy[i].info == 1)ans += 2;
            else ans += 1;
            m -= Copy[i].num;
        }
        if (m==0)break;
    }
    cout<<ans<<endl;

    return 0;
}