小偷进了一个宝库,宝库里有很多财宝,每个财宝有它的价值,也有它的体积。而小偷的背包体积是有限的,装进背包的物品总体积不能超过背包的体积。另外小偷心里有一个规矩,就是每次偷东西,最多只拿K件,多余的不拿。
问该小偷此次偷财宝,一次最多能偷到多大价值的财宝。
第一行是小偷的背包体积C, 0<C<=10000, 为正整数第二行是财宝的体积大小数组W, 0< length(W)< 1000,用空格切分, 每个不大于1000, 为正整数第三行是财宝的价值大小数组P, 0< length(P)< 1000,用空格切分,每个不大于1000, 为正整数第四行是小偷心里的规矩最多数量K, K<=1000, 为正整数
一个整数,小偷一次最多能偷到多大价值的财宝
10 2 3 4 5 12 13 14 15 2
29
取重量为4和5的,累计价值为14+15=29
using System; using System.Collections; public class Programm { public static void Main() { int C = int.Parse(Console.ReadLine());//小偷的背包体积C int[] W = Array.ConvertAll(Console.ReadLine().Split() , int.Parse);//财宝的体积大小数组W int[] P = Array.ConvertAll(Console.ReadLine().Split() , int.Parse);//财宝的价值大小数组P int k =int.Parse(Console.ReadLine());//小偷心里的规矩最多数量K int[,] dp=new int[C+1,k+1]; for(int i=0;i<W.Length;i++) { for(int j=C;j>=0;j--) { for(int o=1;o<=k;o++) { if(j-W[i]>=0&&o-1>=0) { dp[j,o]=Math.Max(dp[j,o], dp[j-W[i],o-1]+P[i]); } } } } Console.WriteLine(dp[C,k]); } }
#include<iostream> #include<sstream> #include<string> #include<algorithm> using namespace std; int dp[1005][1005]; //背包容量为i且拿j个物品时的最大价值 int main() { int bagW, k, t, n = 0; int ws[1005] = { 0 }, gs[1005] = { 0 }; stringstream ss; string s; cin >> bagW; getline(cin, s); getline(cin, s); ss << s; while (ss >> t)ws[n++] = t; ss.clear(); for (int i = 0; i < n; i++) cin >> gs[i]; cin >> k; for (int i = 0; i < n; i++) { for (int j = bagW; j >= ws[i]; j--) { for (int t = 1; t <= k; t++) { //拿取物品数量 dp[j][t] = max(dp[j][t], dp[j - ws[i]][t - 1] + gs[i]); } } } cout << dp[bagW][k] << endl; return 0; }
#include<iostream> #include <sstream> #include<vector> #include<string.h> using namespace std; vector<int> get(string s) { vector<int> a; //把直接输入的字符串转换成流 stringstream str(s); int temp; while (str >> temp) a.push_back(temp); return a; } int f[1000][2]; int main() { int c; cin >> c; getchar(); string v; getline(cin, v); vector<int> vv = get(v); string p; getline(cin, p); vector<int> vp = get(p); int touch; cin>>touch; memset(f, 0,sizeof(f)); for (int i = 0; i < vv.size(); i++) { for (int j = c; j >= vv[i]; j--) { if (f[j][0] > f[j - vv[i]][0] + vp[i]) { f[j][0] = f[j][0]; } else if ((f[j][0] <= f[j - vv[i]][0] + vp[i])) { if (f[j - vv[i]][1] + 1 <= touch) { f[j][1] = f[j - vv[i]][1] + 1; f[j][0] = f[j - vv[i]][0] + vp[i]; } } } } int maxNum = 0; for (int i = 1; i <= c; i++) { maxNum = max(maxNum, f[i][0]); } cout << maxNum << endl; }