首页 > 试题广场 >

无可奈何的小偷

[编程题]无可奈何的小偷
  • 热度指数:219 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小偷进了一个宝库,宝库里有很多财宝,每个财宝有它的价值,也有它的体积。而小偷的背包体积是有限的,装进背包的物品总体积不能超过背包的体积。另外小偷心里有一个规矩,就是每次偷东西,最多只拿K件,多余的不拿。

问该小偷此次偷财宝,一次最多能偷到多大价值的财宝。

输入描述:
第一行是小偷的背包体积C,  0<C<=10000,  为正整数
第二行是财宝的体积大小数组W, 0< length(W)< 1000,用空格切分,  每个不大于1000,  为正整数
第三行是财宝的价值大小数组P, 0<  length(P)< 1000,用空格切分,每个不大于1000,  为正整数
第四行是小偷心里的规矩最多数量K, K<=1000,  为正整数


输出描述:
一个整数,小偷一次最多能偷到多大价值的财宝
示例1

输入

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]);
  }
}

发表于 2022-03-16 23:09:05 回复(0)
#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;
}
编辑于 2022-04-30 10:43:11 回复(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;
}

编辑于 2021-05-16 16:55:33 回复(0)