有个牛牛一起去朋友家吃糖果,第个牛牛一定要吃块糖果.
而朋友家一共只有块糖果,可能不会满足所有的牛牛都吃上糖果。
同时牛牛们有个约定,每一个约定为一个牛牛的编号对,表示第个和第个牛牛是好朋友,他俩要么一起都吃到糖果,要么一起都不吃。
保证每个牛牛最多只出现在一个编号对中。
您可以安排让一些牛牛吃糖果,一些牛牛不吃。
要求使能吃上糖果的牛牛数量最多(吃掉的糖果总量要小于等于),并要满足不违反牛牛们的个约定。
有个牛牛一起去朋友家吃糖果,第个牛牛一定要吃块糖果.
而朋友家一共只有块糖果,可能不会满足所有的牛牛都吃上糖果。
同时牛牛们有个约定,每一个约定为一个牛牛的编号对,表示第个和第个牛牛是好朋友,他俩要么一起都吃到糖果,要么一起都不吃。
保证每个牛牛最多只出现在一个编号对中。
您可以安排让一些牛牛吃糖果,一些牛牛不吃。
要求使能吃上糖果的牛牛数量最多(吃掉的糖果总量要小于等于),并要满足不违反牛牛们的个约定。
第一行个正整数 ,
第二行个正整数 ,
第三行个整数
接下来行,每行两个正整数 ,表示第个牛牛与第个牛牛有约定。
一行一个数字表示最多能吃上糖果的牛牛个数
3 10 5 1 5 1 1 3
2
#include "bits/stdc++.h" using namespace std; class DSU { private : vector<int> f, siz; vector<int> val; public : DSU(int n) : f(n), val(n), siz(n, 1) { iota(f.begin(), f.end(), 0); } int find(int x) { while(x != f[x]) x = f[x] = f[f[x]]; return x; } bool same(int x, int y) { return find(x) == find(y); } bool merge(int x, int y) { x = find(x); y = find(y); if(x == y) return false; siz[x] += siz[y]; val[x] += val[y]; f[y] = x; return true; } int size(int x) { return siz[find(x)]; } int vale(int x) { return val[find(x)]; } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; cin >> n >> m; DSU g(n); for(int i = 0;i < n; i++) cin >> g.val[i]; int k; cin >> k; for(int i = 0;i < k; i++) { int a, b; cin >> a >> b; a--; b--; g.merge(a, b); } vector<int> bag, val; for(int i = 0;i < n; i++) { if(g.find(i) == i) { bag.push_back(g.vale(i)); val.push_back(g.size(i)); } } n = bag.size(); vector<int> dp(m + 1); for(int i = 0;i < n; i++) { for(int j = m;j >= bag[i]; j--) { dp[j] = max(dp[j], dp[j - bag[i]] + val[i]); } } cout << dp.back() << endl; }
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]); } }
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; }
n,m = map(int,input().split()) eat = list(map(int,input().split())) k = int(input()) l = [] for i in range(k): l.append(list(map(int,input().split()))) value = [] weight = [] inbeer = [] for link in l: inbeer.append(link[0]-1) inbeer.append(link[1]-1) weight.append(eat[link[0]-1]+eat[link[1]-1]) value.append(2) for idx,num in enumerate(eat): if idx not in inbeer: value.append(1) weight.append(num) dp = [0]*(m+1) #先遍历物品,在遍历背包 for i in range(len(weight)): for j in range(m,weight[i]-1,-1): dp[j] = max(dp[j],dp[j-weight[i]]+value[i]) print(dp[-1])感觉难点在输入输出数据啊,转化为0-1背包问题。
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; }
n, m = list(map(int, input().split(' '))) cost = list(map(int, input().split(' '))) s = set([i for i in range(n)]) N = int(input()) bulls = [] # 要将结对的牛牛取出来,合并组成新的牛,然后其cost为2个牛牛之和 for _ in range(N): a, b = list(map(int, input().split(' '))) bulls.append((2,cost[a-1] + cost[b-1])) s.remove(a-1) s.remove(b-1) for i in s: bulls.append((1, cost[i])) # 对剩下的牛采用完全背包算法,求出最优化值,其中,dp[i][j]是第i个牛进入后,吃了j块糖果的的最大实际牛牛数 # print(bulls) nn = len(bulls) dp = [0]*(m+1) for i in range(nn): for j in range(m, -1, -1): if j - bulls[i][1] > 0 and dp[j - bulls[i][1]] > 0: if dp[j] < dp[j - bulls[i][1]] + bulls[i][0]: dp[j] = dp[j - bulls[i][1]] + bulls[i][0] else: dp[j] = dp[j] elif j - bulls[i][1] == 0: #边界 dp[j] = max(dp[j], bulls[i][0]) else: dp[j] = dp[j] #print(dp) print(max(dp)) # 5 11 # 4 1 4 2 4 # 2 # 2 4 # 3 5 # 4