总览

买了些什么呢背包算法动态规划
babyre snap xml

题目买了些什么呢

解法

这道题。。感觉本质上是一个算法题，是数学背包问题。
但是我解的时候用的是贪心法，拿代码算出了每一个物品的性价比

然后排名，最后的几个作取舍。也做出来了
但实际上这样的方法是不行的，这道题行只是因为数字不大。
数学背包问题看了别人的博客两篇写的蛮好
https://zhuanlan.zhihu.com/p/349054931
https://blog.csdn.net/qq_40802813/article/details/119579370
学习了这个大问题换成小问题的思想。
即把解决取哪些物品价值最大化变成取不取这个物品对下一个物品的选取的影响的问题。
两篇都有很好的解答，也积累了一些code

#include<iostream>
using namespace std;
int volume[1010], value[1010];//定义储存物品体积和价值的数组 
int ans[1010][1010];//定义储存答案的数组 
int N, V;
int main()
{
	cin >> N >> V;  //输入物品数和背包体积 
	//N = 40;
	//V = 50;
	//int volume[1010] = { 2, 5, 10, 9, 3, 6, 2, 2, 6, 8, 2, 3, 3, 2, 9, 8, 2, 10, 8, 6, 4, 3, 4, 2, 4, 8, 3, 8, 4, 10, 7, 1, 9, 1, 5, 7, 1, 1, 7, 4 };
	//int value [1010] = { 8, 1, 5, 9, 5, 6, 8, 2, 3, 7, 5, 4, 3, 7, 6, 7, 9, 3, 10, 5, 2, 4, 5, 2, 9, 5, 8, 10, 2, 9, 6, 3, 7, 3, 9, 6, 10, 1, 2, 9 };   //物价p 

	for (int i = 1; i <= N; i++)//输入各个物品的属性 
	{
		cin >> volume[i] >> value[i];
	}
	for (int i = N; i >= 1; i--) //从后往前遍历物品求后几个物品的最优解 
	{
		for (int j = 0; j <= V; j++)//因为数组是二维的所以体积怎样遍历都可以 
		{
			ans[i][j] = ans[i + 1][j];
			if (j >= volume[i])
				ans[i][j] = max(ans[i][j], ans[i + 1][j - volume[i]] + value[i]);//状态转移方程 
		}
	}
	int nowvolume = V;//记录当前体积 
	for (int i = 0; i < N; i++)//从第一个物品开始遍历 
	{
		if (volume[i] <= nowvolume && ans[i][nowvolume] == ans[i + 1][nowvolume - volume[i]] + value[i])
		{//判段这个物品是否可选能选就选尽量选小同时要确保当前背包体积能装下此物品 
			cout << i << " ";//输出物品编号 
			nowvolume -= volume[i];//选择一个物品当前体积要相应减少 
		}
	}
	return 0;
}

/*#include<iostream>
using namespace std;
int f[10][10];//状态函数f[i][j]表示第i件物品容量为j最大价值
int v[100];
int w[100];

函数功能：求0-1背包问题的最大价值
函数形参：物品数量和背包容量
函数返回值：返回最大值

int fun(int n, int m)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (j < w[i])
				f[i][j] = f[i - 1][j];
			else
			{
				int a = f[i - 1][j];
				int b = f[i - 1][j - w[i]] + v[i];
				if (a > b)
				{
					f[i][j] = a;
					cout << "第" << i << "个不放"<<endl;
				}
				else
				{
					f[i][j] = b;
					cout << "第" << i << "个放"<<endl;

				}
			}
				//f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
		}

	}
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			if(f[i][j]!=11231)
				cout << f[i][j] << " ";
		}
	return f[n][m];

}
/*
int main()
{
	int n, m; //m是总容量 n物品数
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	cout << fun(n, m);
	return 0;
}
*/


//int w[41] = { 2, 5, 10, 9, 3, 6, 2, 2, 6, 8, 2, 3, 3, 2, 9, 8, 2, 10, 8, 6, 4, 3, 4, 2, 4, 8, 3, 8, 4, 10, 7, 1, 9, 1, 5, 7, 1, 1, 7, 4 };
//int p[41] = { 8, 1, 5, 9, 5, 6, 8, 2, 3, 7, 5, 4, 3, 7, 6, 7, 9, 3, 10, 5, 2, 4, 5, 2, 9, 5, 8, 10, 2, 9, 6, 3, 7, 3, 9, 6, 10, 1, 2, 9 };   //物价p

上面那个可以找找路径
下面那个用来求最大价值
但对于这个题目，还有个更好的code 是别人的wp

n = 40  
capacity = 50  

weights = [2, 5, 10, 9, 3, 6, 2, 2, 6, 8, 2, 3, 3, 2, 9, 8,  
          2, 10, 8, 6, 4, 3, 4, 2, 4, 8, 3, 8, 4, 10, 7, 1,  
          9, 1, 5, 7, 1, 1, 7, 4, 3]
values = [8, 1, 5, 9, 5, 6, 8, 2, 3, 7, 5, 4, 3, 7, 6, 7,  
          9, 3, 10, 5, 2, 4, 5, 2, 9, 5, 8, 10, 2, 9, 6, 3,  
          7, 3, 9, 6, 10, 1, 2, 9, 4]

dp = [[0 for j in range(capacity + 1)] for i in range(n + 1)]

for i in range(1, n + 1):
    for j in range(capacity + 1):
        if weights[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1],
                           dp[i - 1][j - weights[i - 1]] - values[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]

result = []
j = capacity
for i in range(n, 0, -1):
    if dp[i][j] != dp[i - 1][j]:
        result.append(i)
        j -= weights[i - 1]

print(result[::-1])

出flag

自行-1