176

[//]: # 最简单的01背包问题（C语言）

### 二维代码

#include <stdio.h>
#include <stdlib.h>

#define N 1010

int n, m;       // n为物品，m为背包体积
int v[N], w[N]; // v是对应物品体积，w是对应物品价值（权重，重量）
int f[N][N];    // dp的数组

int main()
{

scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &v[i], &w[i]);
}

for (int i = 1; i <= n; i++)     // 遍历物品
for (int j = 0; j <= m; j++) // 遍历体积
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = f[i][j] >= f[i - 1][j - v[i]] + w[i] ? f[i][j] : f[i - 1][j - v[i]] + w[i];
}

printf("%d\n", f[n][m]);
return 0;
}
*/


#### 代码的巧妙地方

C++中不存在这个问题

c99标准：
If an object that has automatic storage duration is not initialized explicitly, its value isindeterminate. If an object that has static storage duration is not initialized explicitly,then:
— if it has pointer type, it is initialized to a null pointer;
— if it has arithmetic type, it is initialized to (positive or unsigned) zero;
— if it is an aggregate, every member is initialized (recursively) according to these rules;
— if it is a union, the first named member is initialized (recursively) according to theserules.

for (int i = 1; i <= n; i++) // 遍历物品 for (int j = 0; j <= m; j++) // 遍历体积

j需要从背包体积为0一直计算到背包的总体积m

### 一维代码

#include <stdio.h>
#include <stdlib.h>

#define N 1010

int n, m;       // n为物品，m为背包体积
int v[N], w[N]; // v是对应物品体积，w是对应物品价值（权重，重量）
int f[N];    // dp的数组

int main()
{

scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &v[i], &w[i]);
}

for (int i = 1; i <= n; i++)     // 遍历物品
for (int j = m; j >= v[i]; j--) // 遍历体积
{

f[j] = f[j] >= f[j - v[i]] + w[i] ? f[j] : f[j - v[i]] + w[i];
}

printf("%d\n", f[m]);
return 0;
}


2个月前

### 786 第k个数

#### C 代码（最终版）

#include<stdio.h>
#define Maxsize 100000

int k_num(int a[],int l,int r,int k)
{
if(l>=r)return a[l];
int i = l-1, j = r+1, x = a[l+r>>1];
while(i<j)
{
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j)
{
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
if(k<=j)return k_num(a,l,j,k);
else return k_num(a,j+1,r,k);
}

int main()
{
int n,k,res;
int a[Maxsize];
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
res = k_num(a,0,n-1,k-1);
printf("%d\n",res);
return 0;
}


    if(k<=j)return k_num(a,l,j,k);
else return k_num(a,j+1,r,k);


## 递归我感觉就是要装作糊涂一点，我以前总喜欢一步一步推到最后一个返回的过程，但是就把自己绕进去了，其实像这个就是一句话的事：要是左侧<=x的数中包含下标k就继续找这个区间，否则去另外一个区间找。思维上能走通，代码上能体现出大局观就行，因为这时已经对了，不用自己再去试几组数然后带进去验证总结一般规律。

#### C 代码（第一次的版本）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define Maxsize 100000

int k_num(int a[], int l, int r, int k)
{
if (k > (r-l + 1))return -1;
if (l >= r) return a[l];
int i = l - 1, j = r + 1, x = a[l + r >> 1];
while (i < j)
{
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j)
{
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
if (i == j) {
if (j - l + 1 == k)return a[j];
}
if (j - l + 1 < k)return k_num(a, j + 1, r, k-(j-l+1));
else return k_num(a, l, j, k);

}

int main()
{
int n, k, res;
int a[Maxsize];
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
res = k_num(a, 0, n - 1, k);
printf("%d\n", res);
return 0;
}


    if (i == j) {
if (j - l + 1 == k)return a[j];
}
if (j - l + 1 < k)return k_num(a, j + 1, r, k-(j-l+1));
else return k_num(a, l, j, k);


2个月前

### 785.快速排序 代码注意部分

#### C++ 代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define Maxsize 100000

void quick_sort(int a[], int l, int r)
{
if (l >= r)return;
int i = l - 1, j = r + 1, x = a[l + r >> 1]; //这里注意右移一位代表除以2，如果写为>>2，那么x可能在判断的数组范围之外比较错误，从而导致排序错误
while (i < j) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) {
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
}
//这里如果写成swap函数需要使用指针传参，否则a数组内部不会改变
}
//while完成之后i左侧全都<=x，j右侧全都>=x
quick_sort(a, l, j);//注意右边界是j
quick_sort(a, j + 1, r);
}

int main() {
int n;
int a[Maxsize];
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}


2个月前